Analysis
因为有环,所以可以先tarjan算法求出e-DCC(边双连通分量),这个时候就要去染色, 这时候我们就要思考对于每一个分量我们需要多少种颜色,其实不难看出,如果存在奇环 (就像1->2->3->4->1,我们发现如果仅用两种颜色,是没办法使每条边两端的端点的颜 色不同),于是对于每一个连通分量跑一次dfs,如果存在奇环,说明要用三种颜色才能满足。
代码实现
#include using namespace std; const int N=1e4+10; int n,cnt,tot,scc,ans=2,m; int h[N],nex[N],dfn[N],eg[N],low[N],id[N],col[N],ver[N]; inline void add(int x,int y) { nex[tot]=h[x]; ver[tot]=y; h[x]=tot++; } inline void tarjan(int u,int deg) { dfn[u]=low[u]=++cnt; for (int i=h[u];~i;i=nex[i]) { int j=ver[i]; if(!dfn[j]) { tarjan(j,i); low[u]=min(low[u],low[j]); if(dfn[u]<low[j]) eg[i]=eg[i^1]=1; } else if(i!=(deg^1)) low[u]=min(low[u],dfn[j]); } } inline void dfs(int u) { for (int i=h[u];~i;i=nex[i]) { int j=ver[i]; if(!col[j]) { col[j]=3-col[u]; dfs(j); } else if(col[j]==col[u]) ans=3; } } int main() { memset(h,-1,sizeof(h)); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y),add(y,x); } for (int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0); for (int i=1;i<=n;i++) if(!col[i]) col[i]=1,dfs(i); printf("%d\n",ans); return 0; }
后话
我相信这只是其中一种解法,但是对我来说比较好理解,如果有不足之处也请各位多多包涵