URAL 1320 Graph Decomposition（并查集）

1320. Graph Decomposition

Time limit: 0.5 second
Memory limit: 64 MB

There is a simple graph with an even number of edges. You are to define if it is possible to present it by the set of pairs of adjacent edges (having a common vertex).

Input

contains a sequence of the numbers pairs. Each pair denotes vertices identifiers of one edge. All the identifiers are integers from 1 to 1000. You may assume that there are no loops and multiple edges in the graph defined by the input data.

Output

“1” (without quotation marks), if the decomposition is possible and “0” otherwise.

Samples

input	output
1 2 2 3 3 1 1 10	1
1 2 2 3 3 1 4 10	0

Problem Author: Idea: Alexander Petrov, prepared by Alexander Petrov, Leonid Volkov

【分析】每次删除相邻的两条边，问是否能全部删除干净。偶数条边，每条边两个顶点，也就是说如果能删除干净，则每个连通块中所有点的度数之和能够整除4.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 1005;
const int M = 24005;
int edg[N][N],vis[N];
int in[N],parent[N],n;
int Find(int x)
{
    if(parent[x]!=x)parent[x]=Find(parent[x]);
    return parent[x];
}
void Union(int x,int y)
{
    x=Find(x);y=Find(y);
    if(x==y)return;
    parent[y]=x;
}
int main()
{
    int u,v,num=1;
    for(int i=1;i<N;i++)parent[i]=i;n=0;
    while(~scanf("%d%d",&u,&v)){
        Union(u,v);
        in[u]++;in[v]++;
        n=max(n,max(u,v));
    }
    bool ok=true;
    for(int i=1;i<=n;i++){
        vis[Find(i)]+=in[i];
    }
    for(int i=1;i<=n;i++){
        if(vis[Find(i)]%4!=0)ok=false;
    }
    if(ok)puts("1");
    else puts("0");
    return 0;
}