其实是一道挺不错的题，难度不大，但还是需要思考。
首先要明白，既然要封锁所有的路，就要保证对于每一条路，其两个端点至少要有一个被染色。
那问题就迎刃而解了，从一个点开始，每次给相邻的点染上不同的颜色，最后判断染哪一个色结果最优就好了。
但是这道题有一个坑点，害的我没有一次切掉……
题目原话：
“阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。”
但是事实上，这些点不一定都在图里，而且，它们不一定在一个图里！！！
emmm……
还有，数组按照数据开（保证比数据大一点）有一个点会RE，所以我改成了10倍的才AC。
这不就是想坑我的AC率么……
代码：
#include<cstdio> #include<iostream> #include<cstdlib> using namespace std; int head[100005],nxt[1000005],to[1000005],col[1000005],vis[100005]; int cnt,n,m,ans,num,sum; bool flag; void add(int a,int b) { to[++cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; } void search(int u) { num++; for(int i=head[u]; i; i=nxt[i]) { int v=to[i]; if(col[v]==col[u]) { printf("Impossible "); flag=1; exit(0); return ; } if(col[v]==3) { if(col[u]==1) col[v]=2; else { col[v]=1; ans++; } search(v); } } } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) col[i]=3; for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); vis[x]=1; vis[y]=1; } for(int i=1; i<=n; i++) { if(vis[i]&&col[i]==3) { num=0; ans=1; col[i]=1; search(i); sum+=min(ans,num-ans); } } if(flag==1) return 0; printf("%d",sum); return 0; }