洛谷-图的遍历-P1330 封锁阳光大学

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<string>
 5 #include<string>
 6 #include<algorithm>
 7 using namespace std;
 8 struct Edge
 9 {
10     int t;
11     int nexty;
12 }edge[200000];
13 int head[20000];
14 int cnt=0;//链式前向星
15 void add(int a,int b)//存边
16 {
17     cnt++;
18     edge[cnt].t=b;
19     edge[cnt].nexty=head[a];
20     head[a]=cnt;
21 }
22 bool used[20000]={0};//是否遍历过
23 int col[20000]={0};//每一个点的染色
24 int sum[2];//黑白两种染色各自的点数
25 bool dfs(int node,int color)//染色（返回false即impossible）
26 {
27     if(used[node])//如果已被染过色
28     {
29         if(col[node]==color)return true;//如果仍是原来的颜色，即可行
30         return false;//非原来的颜色，即产生了冲突，不可行
31     }
32     used[node]=true;//记录
33     sum[col[node]=color]++;//这一种颜色的个数加1，且此点的颜色也记录下来
34     bool tf=true;//////////////////////////////////////////////////是否可行,,,巧妙 
35     for(int i=head[node];i!=0&&tf;i=edge[i].nexty)//遍历边
36     {
37         tf=tf&&dfs(edge[i].t,1-color);////////////////////////////////是否可以继续染色
38     }
39     return tf;//返回是否完成染色
40 }
41 int main()
42 {
43     int n,m;
44     scanf("%d%d",&n,&m);
45     int a,b;
46     while(m--)
47     {
48         scanf("%d%d",&a,&b);
49         add(a,b);
50         add(b,a);//存的是有向边，所以存两次
51     }
52     int ans=0,minn;
53     for(int i=1;i<=n;i++)
54     {
55         if(used[i])continue;//如果此点已被包含为一个已经被遍历过的子图，则不需重复遍历
56         sum[0]=sum[1]=0;//初始化
57         if(!dfs(i,0))//如果不能染色
58         {
59             printf("Impossible");
60             return 0;//直接跳出
61         }
62         minn=min(sum[0],sum[1]);//加上小的一个
63         ans+=minn;
64     }
65     printf("%d",ans);//输出答案
66     return 0;
67 }