首页 > 代码库 > 1013. Battle Over Cities
1013. Battle Over Cities
好久都没有做题了,从长沙回来之后一直就是看看QT,感觉自己真的要蠢死了><不开心不开心
题目大概意思就是从一个图里面去掉一个点,看看剩下多少个孤立点。
自己想了好大一会儿没有思路,看到网上一个代码,真是惊叹好神奇...><
用遍历的方式,如DFS,将去掉的点设为1,然后遍历一次看看剩下多少个没有被遍历到的点。
#include <iostream> #include <cstring> using namespace std; #define MAX_VERTEX_NUM 1005 int visit[MAX_VERTEX_NUM]; typedef struct { int vexs[MAX_VERTEX_NUM]; bool edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,edgenum; }MGraph; MGraph g; void dfs(int from){ int i; for(i=1;i<=g.vexnum;i++){ if(i!=from&&visit[i]==0&&g.edges[from][i]==1){ visit[i]=1; dfs(i); } } } int main() { int n,k,m,city,count; cin>>n>>m>>k; g.vexnum=n; g.edgenum=m; memset(g.edges,0,sizeof(g.edges)); int c1,c2; for(int i=0;i<m;i++){ cin>>c1>>c2; g.edges[c1][c2]=g.edges[c2][c1]=true; } for(int i=0;i<k;i++){ count=0; memset(visit,0,sizeof(visit)); cin>>city; visit[city]=1; for(int j=1;j<=n;j++){ if(visit[j]==0){ count++; dfs(j); } } count=count-1; cout<<count<<endl; } return 0; }
1013. Battle Over Cities
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。