1320. Graph Decomposition

怼烎@ 2022-01-05 15:41 141阅读 0赞

## 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 ###

<table style="border:1px solid #000000;border-collapse:collapse;"> 
 <tbody> 
  <tr> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">input</th> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">output</th> 
  </tr> 
  <tr> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>1 2
2 3
3 1
1 10
</pre> </td> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>1
</pre> </td> 
  </tr> 
  <tr> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>1 2
2 3
3 1
4 10
</pre> </td> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>0
</pre> </td> 
  </tr> 
 </tbody> 
</table>

**Problem Author:**Idea: Alexander Petrov, prepared by Alexander Petrov, Leonid Volkov **Problem Source:**VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

并查集&&计算相应根节点的度数和。

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<string>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<cstdio>
     6 using namespace std;
     7 int fa[10001];
     8 int de[10001];
     9 int a,b,i,j,k;
    10 void make()
    11 {
    12     for(i=1;i<=10001;i++)
    13      fa[i]=i;
    14 }
    15 int find(int x)//并查集
    16  {
    17      if(fa[x]!=x)
    18       fa[x]=find(fa[x]);
    19      if(fa[x]==x)
    20       return fa[x];
    21 }
    22 void uon(int x,int y)
    23  {
    24      x=find(fa[x]);
    25      y=find(fa[y]);
    26      if(x!=y)
    27       {
    28           fa[y]=x;
    29           de[x]+=de[y];//计算相应根节点的度数
    30           de[y]=0;
    31       }
    32  }
    33 int main()
    34 {
    35     make();
    36     memset(de,0,sizeof(de));
    37     while(scanf("%d %d",&a,&b)!=EOF)
    38      {
    39          uon(a,b);
    40          de[find(b)]++;
    41      }
    42      for(i=1;i<10001;i++)
    43       if(de[i]%2)//不为偶数不满足条件
    44        {
    45            cout<<'0'<<endl;
    46            return 0;
    47        }
    48      cout<<'1'<<endl;
    49      return 0;
    50 
    51 }

转载于:https://www.cnblogs.com/sdau--codeants/p/3259601.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/3babab0b1f68408fb98937bb2abc6565.png