牛客算法周周练20 F- tarjan+奇环

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;
}

后话

我相信这只是其中一种解法，但是对我来说比较好理解，如果有不足之处也请各位多多包涵