C++14(g++5.4) 解法, 执行用时: 265ms, 内存消耗: 12664K, 提交时间: 2020-06-16 20:39:54

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
 
int f[N];
vector<int> G[N];

void dfs(int x){
    int sum=0;
    for(auto i:G[x]){
        if(!f[i]) f[i]=f[x]^3,dfs(i);
        if(f[i]==f[x]) sum++;  
    }
    if(sum>=2) f[x]^=3;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(f,0,sizeof(f));
    for(int i=n;i>=1;i--) if(!f[i]) f[i]=1,dfs(i);
    for(int i=1;i<=n;i++) cout<<f[i]<<" \n"[i==n];
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 198ms, 内存消耗: 9724K, 提交时间: 2020-06-16 19:42:19

#include<bits/stdc++.h>
using namespace std;

vector<int>R[100005];
bool V[100005]={0},T[100005]={0};
void DFS(int x)
{
	int i,j,k=0;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(!V[j])V[j]=1,T[j]=!T[x],DFS(j);
		if(T[j]==T[x])k++;
	}
	if(k>1)T[x]^=1;
}
int main()
{
    int i,j,n,m; 
    scanf("%d%d",&n,&m);
    while(m--)
    {
    	scanf("%d%d",&i,&j);
    	R[i].push_back(j),R[j].push_back(i);
	}
	for(i=1;i<=n;i++)if(!V[i])DFS(i);
	for(i=1;i<=n;i++)printf("%d ",T[i]+1);
}