Wannafly挑战赛27B（DFS，链表头插法）

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
int flag=0;
int to[400007],nex[400007],vis[100007],head[100007];
void add(int a,int b){//链表的头插法，nex数组开成next交的时候会编译错误
    to[++cnt]=b;
    nex[cnt]=head[a];
    head[a]=cnt;
}
void dfs(int a,int b){
    for(int i=head[a];i!=0;i=nex[i]){//遍历这个点的邻接点
        int v=to[i];
        if(v==b)//此前在b的邻接点中已经遍历过该情况
            continue;
        if(vis[v]){//说明有环
            int x=vis[a];
            if((x-vis[v]+1)&1)//环的长度为奇数，这个时候需要三种颜色
                flag=1;
            return;
        }
        vis[v]=vis[a]+1;
        dfs(v,a);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    vis[1]=1;
    dfs(1,0);
    if(n==1)
        printf("1");
    else if(flag==1)
        printf("3");
    else if(flag==0)
        printf("2");
    return 0;
}

巴特西

Wannafly挑战赛27B（DFS，链表头插法）

最新文章

热门文章