codeforce 272E Dima and Horses （假DFS）
codeforce 272E Dima and Horses （假DFS）
E. Dima and Horses
Dima came to the horse land. There are n horses living in the land. Each horse in the horse land has several enemies (enmity is a symmetric relationship). The horse land isn't very hostile, so the number of enemies of each horse is at most 3.
Right now the horse land is going through an election campaign. So the horses trusted Dima to split them into two parts. At that the horses want the following condition to hold: a horse shouldn't have more than one enemy in its party.
Help Dima split the horses into parties. Note that one of the parties can turn out to be empty.
Input
The first line contains two integers n, m
— the number of horses in the horse land and the number of enemy pairs.
Next m lines define the enemy pairs. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), which mean that horse ai is the enemy of horse bi.
Consider the horses indexed in some way from 1 to n. It is guaranteed that each horse has at most three enemies. No pair of enemies occurs more than once in the input.
Output
Print a line, consisting of n characters: the i-th character of the line must equal "0", if the horse number i needs to go to the first party, otherwise this character should equal "1".
If there isn't a way to divide the horses as required, print -1.
Examples
input
3 3
1 2
3 2
3 1output
100input
2 1
2 1output
00input
10 6
1 2
1 3
1 4
2 3
2 4
3 4output
0110000000
假如一开始都是0那一组，然后开始遍历，到某一点与0这组里面冲突的有两个，那么就要把这个放到1这一组，找暴力第一组如果第一组也有两个冲突，那么在把跟他冲突的那个调到第一组，重复这个操作，完成假DFS即可，其实就是递归。
#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
//---------------------------------Sexy operation--------------------------//
#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define debug(n) printf("%d_________________________________\n",n);
#define speed ios_base::sync_with_stdio(0)
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
//-------------------------------Actual option------------------------------//
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Swap(a,b) a^=b^=a^=b
#define Max(a,b) (a>b?a:b)
#define Min(a,b) a<b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define mp(a,b) make_pair(a,b)
#define pb(n) push_back(n)
//--------------------------------constant----------------------------------//
#define INF 0x3f3f3f3f
#define esp 1e-9
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef long long ll;
//___________________________Dividing Line__________________________________//
const int maxn=300005;
int n,m,v[maxn]; //一开始全是0
vector<int>a[maxn];
void dfs(int x)
{
int n=a[x].size(),cnt=0;
for(int i=0; i<n; i++)
if(v[a[x][i]]==v[x]) cnt++;
if(cnt>=2)//在1里面有两个敌对，把他扔到2里
{
v[x]=!v[x];
for(int i=0; i<n; i++)
if(v[x]==v[a[x][i]]) dfs(a[x][i]);
}
}
int main()
{
cini(n),cini(m);
for(int i=1; i<=m; i++)
{
int x,y;
cini(x),cini(y);
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1; i<=n; i++)
dfs(i);
for(int i=1; i<=n; i++)
printf("%d",v[i]);
}腾讯云开发者
