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<=1000000C++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':' '); }