列表

详情


NC14830. 珂朵莉的二分图

描述

珂朵莉给你一个无向图

其有n个点,m条边

对于每条边,她想知道删了这条边之后这个图是不是一个二分图

输入描述

第一行两个整数n,m
之后m行,每行两个数x,y表示有一条x和y之间的无向边
第i个边的序号即为i

输出描述

第一行输出一个整数,表示有多少边满足条件
接下来一行,从小到大输出这些边的序号
如果没有边满足条件,只输出一行一个数0,注意不要多输出换行

示例1

输入:

4 4
1 2
1 3
2 4
3 4

输出:

4
1 2 3 4

说明:

对于100%的数据,有n , m<=1000000

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 1037ms, 内存消耗: 86160K, 提交时间: 2020-01-05 23:55:32

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
const int maxn=1000005;
struct node
{
	int v,id,next;
}e[2*maxn];
int head[maxn],tot;
void add(int u,int v,int id)
{
	e[tot].v=v,e[tot].id=id,e[tot].next=head[u],head[u]=tot++;
}
int n,m,dep[maxn],num[maxn],vis[maxn],cir,self,not_tree;
vector<int>ans;
void dfs(int u,int fa)
{
	vis[u]=1;
	for(int i=head[u];~i;i=e[i].next)
	{
		if(i==fa)continue;
		int v=e[i].v;
		if(!vis[v])
		{
			dep[v]=dep[u]+1;
			dfs(v,i^1);
			num[u]+=num[v];
		}
		else
		{
			if(dep[v]>dep[u])continue;
			if((dep[u]-dep[v]+1)&1)num[u]++,num[v]--,cir++,not_tree=e[i].id;
			else num[u]--,num[v]++;
		}
	}
}
void dfs1(int u,int fa)
{
	vis[u]=1;
	if(num[u]==cir)ans.push_back(e[fa].id);
	for(int i=head[u];~i;i=e[i].next)
		if(!vis[e[i].v])dfs1(e[i].v,i);
}
int main()
{
    //freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	tot=0;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(u==v)self++,ans.push_back(i);
		else add(u,v,i),add(v,u,i);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			dep[i]=1;
			dfs(i,-1);
		}
	if(!cir)
	{
		if(self==0)
		{
			printf("%d\n",m);
			for(int i=1;i<=m;i++)printf("%d%c",i,i==m?'\n':' ');
		}
		else if(self==1)printf("1\n%d\n",ans[0]);
		else printf("0\n");
	}
	else
	{
		if(self)printf("0\n");
		else
		{
			memset(vis,0,sizeof(vis));
			for(int i=1;i<=n;i++)
				if(!vis[i])dfs1(i,-1);
			if(cir==1)ans.push_back(not_tree);
			printf("%d\n",ans.size());
			sort(ans.begin(),ans.end());
			for(int i=0;i<ans.size();i++)printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 628ms, 内存消耗: 86784K, 提交时间: 2018-01-01 20:21:19

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+88;
bool vis[N];
int n,m,cnt,ans[N];
int head[N],tot=2,top;
int bian[N<<1],f[N],g[N],pos[N];
struct node{
	int to,next;
}e[N<<1];
void add(int u,int v){
	e[tot].to=v;e[tot].next=head[u];head[u]=tot++;
}
void dfs(int c,int et){
	vis[c]=1;
	pos[c]=++top;
	for(int i=head[c];i;i=e[i].next){
		if(bian[i]==-1) continue;
		if(!vis[e[i].to]) {
			bian[i]=bian[i^1]=-1;
			dfs(e[i].to,i>>1);
			f[et]+=f[i>>1];
			g[et]+=g[i>>1];
		}
		else {
			if(bian[i]==1) --f[et];
			else if(bian[i]==2) --g[et];
			else if(!bian[i]) {
				if((pos[c]-pos[e[i].to])&1) ++g[et],bian[i]=bian[i^1]=2;
				else ++f[et],++cnt,bian[i]=bian[i^1]=1;
			}
		}
	}
	--top;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;++i) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;++i) if(!vis[i]) dfs(i,0);
	int sum=0;
	if(!cnt) for(int i=1;i<=m;++i) ans[sum++]=i;
	else {
		for(int i=1;i<=m;++i) 
		if(f[i]==cnt&&g[i]==0) ans[sum++]=i;
		else if(cnt==1&&bian[i<<1]==1) ans[sum++]=i;
	}
	printf("%d\n",sum);
	for(int i=0;i<sum;++i) printf("%d%c",ans[i],i==sum-1?'\n':' ');
}

上一题