洛谷P1330 封锁阳光大学
dfs染色 图论
对于每一个连通块 进行单独 染色，选取两种颜色中较少的作为河蟹，加入答案
需要注意本题中不一定是连通图，有可能有多个连通分量
1 #include <bits/stdc++.h> 2 #define LL long long 3 #define For(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std ; 5 6 const int N = 10011 , M = 100011 ; 7 struct edge{ 8 int to,pre ; 9 }e[M*2] ; 10 int head[N],visit[N],color[N] ; 11 int n,m,cnt,mi,sum,ans,all,white ; 12 13 inline LL read() 14 { 15 LL x = 0 , f = 1 ; 16 char ch = getchar() ; 17 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 18 while(ch>='0'&&ch<='9') { x=x * 10 + ch-48 ; ch = getchar() ; } 19 return x * f ; 20 } 21 22 inline void add(int x,int y) 23 { 24 e[cnt].to = y ; 25 e[cnt].pre = head[x] ; 26 head[x] = cnt++ ; 27 } 28 29 inline void init() 30 { 31 n = read() ; m = read() ; 32 For(i,0,N-1) head[ i ] = -1 ; 33 int x,y ; 34 For(i,1,m) { 35 x = read() ; y = read() ; 36 add(x,y) ; add(y,x) ; 37 } 38 39 } 40 41 inline void dfs(int u) 42 { 43 int v ; 44 all++ ; 45 for(int i=head[u];~i;i=e[i].pre ) { 46 v = e[ i ].to ; 47 if(!visit[ v ]) { 48 visit[ v ] = 1 ; color[ v ] = !color[ u ] ; 49 white+=color[ v ] ; // 颜色为 1 的点 50 dfs(v) ; 51 } 52 else{ 53 if(!color[ u ]!=color[ v ]) { 54 printf("Impossible ") ; 55 exit( 0 ) ; 56 } 57 } 58 } 59 } 60 61 int main() 62 { 63 init() ; 64 For(i,1,n) 65 if(!visit[ i ]) { 66 visit[ i ] = 1 ; color[ i ] = 0 ; 67 all = 0 ; white = 0 ; 68 dfs( i ) ; 69 mi = min( white,all-white ) ; 70 ans+=mi ; 71 } 72 73 printf("%d ",ans) ; 74 return 0 ; 75 }