Description
Statements
Yuriy is a corrupted head of police. Every day he has to set policemen to the posts in the city so that local gangs still could commit crimes. The city has n squares connected by m streets so that the j-th street connects the aj-th and the bj-th squares. A policeman, being set on some square, can observe this square and also all squares connected with it. Yuriy wants to set policemen in such a way that at least one square is not observed, which lets the gangs to do their dark business on this square. Of course, Yuriy doesn't want to be suspicious, so he plans to set policemen to as many squares as possible.
Input
The first line contains two space-separated integers: n and m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105) — the numbers of squares and streets in the city.
Each of the next m lines contains two space-separated integers: aj and bj (1 ≤ aj, bj ≤ n, aj ≠ bj) — the numbers of squares connected by the j-th street. Every pair of squares can be connected by at most one street.
Output
Output n space-separated integers. On the i-th position output 1, if a policeman should be set to the i-th square, or 0 if it shouldn't be done. If there are many possible solutions, output any of them.
Sample Input
5 5 1 2 2 3 3 4 4 5 5 1
0 0 1 1 0
6 4 1 2 3 4 3 5 3 6
0 0 1 1 1 1
找到出度最小的那一条边，作为空点，与其相连的为0，其他的为1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
vector<ll> g[200005];
ll a1[200005];
ll inde[200005];
int main()
{
int minn = inf_int;
int st = 0;
ll n,m,a,b;
cin >> n >> m;
for(int i=0;i<m;i++)
{
cin >> a >> b;
inde[a]++;
inde[b]++;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=0;i<=n;i++)
a1[i] = 1;
for(int i=1;i<=n;i++)
{
if(minn>inde[i])
{
minn = inde[i];
st = i;
}
}
for(int i=0;i<g[st].size();i++)
{
int t1 = g[st][i];
a1[t1] = 0;
}
a1[st]=0;
for(int i=1;i<=n;i++)
{
printf("%lld ",a1[i]);
}
return 0;
}