2021 年百度之星·程序设计大赛 - 初赛二 1003 魔怔（并查集，联通性，欧拉回路）

problem

solution

• 发现除了起点和终点，剩下所有点周围的边都会被恰经过偶数次，所以这些点初始连向了偶数条白边。
• 考虑由白边连接形成的图，每个连通块中度数为奇数的点一定为偶数个。
• 所以起点所在连通块最多有两个点度数为奇数，且包含起点，不包含起点的连通块不能有点度数为奇数。（或者由欧拉回路的性质可得，如果有大于两个度为奇数的点一定是不能完成任务的）
• 所以每个包含白边的连通块都可以一笔画，每条白边都恰经过一次且不会经过黑边。答案即为 白边个数 +2 ( 包含白边或包含起点的连通块个数 -1)。

//没补完.jpg
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1010;

int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

int e[maxn][maxn], in[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;  cin>>T;
    while(T--){
        memset(e,0,sizeof(e));
		memset(in,0,sizeof(in));
        
        int n, rt;  cin>>n>>rt;
        int cnt = 0;  init(n);
        for(int i = 2; i <= n; i++){
            string s;  cin>>s;
            for(int j = 0; j < i-1; j++){
                e[i][j+1] = e[j+1][i]= s[j]-'0';
                if(e[i][j+1]==0){
                    cnt++;   
                    in[i]++;  in[j+1]++;//累加度数
                    merge(i,j+1);
                }
            }
        }
        //cout<<cnt+2<<"\n";
        
        LL ans = 0, sum = 0, ok=0;
        map<int,int>mp;
        for(int i = 1; i <= n; i++){
            if(in[i]%2==1)ans++;
            sum += in[i];
            if(in[i]){
                int s = find(i);
                if(mp[s]==0){ok++; mp[s]=1;}
            }
        }
        if(sum==0){cout<<"0\n"; continue;}
        sum = sum/2+(ok-1)*2;
        if(ans>2){cout<<"-1\n"; continue;}
        else{
            if(in[rt]){//在
                if(in[rt]%2==0){//偶数
                    if(ans)cout<<"-1\n";
                    else cout<<sum<<"\n";
                }else{//奇数
                    cout<<sum<<"\n";
                }
            }else{//不在
                if(ans==0)cout<<sum+2<<"\n";
                else cout<<"-1\n";
            }
        }
        
        
        continue;
        for(int i = 1; i <= n; i++){
            for(int j=1; j <= n; j++)cout<<e[i][j]<<" ";
            cout<<"\n";
        }
    }
    
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/119357806