2603: 干扰者病毒
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：51
解决：22
题目描述
题目描述
在M星球上建立了很多通信基站，这些基站组成了通信网络。
近期出现了一种名为“干扰者”的病毒，它们能够入侵并破坏基站间的通信。
通信网络可以看作是由 nn 个基站构成的无向图，基站编号从1~n，通过 m 条线路相连。每个“干扰者”病毒都可以选择一个基站进行破坏，当某个基站被破坏后，与这个基站相连的线路就会被切断。但病毒有个奇妙的现象，如果它们选择了相邻的两个基站，就会产生冲突。
请你找出至少需要多少个“干扰者”病毒，才能切断所有线路并避免病毒冲突。
提示：任选一点开始放置病毒，满足则表示线路能全部切断，相反则不存在。
输入描述
第一行两个正整数 n 和 m，分别表示基站的数量和线路的数量。
接下来 m 行，每行两个整数 u 和 v，表示基站 u 和基站 v 之间存在一条线路。
输出描述
如果“干扰者”病毒无法封锁所有线路，则输出 “Impossible”；否则，输出一个整数，表示至少需要多少个“干扰者”病毒。
样例输入 复制
7 6
1 4
3 5
1 3
5 4
2 5
6 7样例输出 复制
3提示
/*
依次枚举每个点；若没有被标记过则处理
怎么处理呢？利用广搜01交替标记结点
例如第一层标记1，第二层标记0，第三层标记1
冲突情况：相连且标记数字相同
最后返回1的数量或0的数量，谁小返回谁 */
int G[100][100];
int vis[100];//标记有没有被访问过
bool f[100] ;//标记01情况的
int n,m,u,v,w,x,y,z;
int bfs(int u){//返回-1表示 冲突，大于0，则是病毒数量
queue<int> q;
int s[2]={0,1};//用于统计0的数量和1的数量
q.push(u);
vis[u]=f[u]=1;//标记u已经处理，标记u的数字为1
while(q.size()){
//取队头元素并出队
for(int v=1;v<=n;v++){
//相连且颜色一致 则冲突
//相连且没有被处理过
//1变0 0变1
//统计1或0的数目
//入队
}
}
}
return min(s[0],s[1]);//返回数量小的
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;
G[u][v]=G[v][u]=1;
}
int ans=0;
for(int i=1;i<=n;i++){//枚举每个点
if(vis[i]==0){//没有被标记则，需要用广搜标记
int x=bfs(i);//取病毒数量
if(x==-1){
cout<<"Impossible";
return 0;
}
ans+=x;
}
}
cout<<ans;
return 0;
}