1013. Battle Over Cities (25)
2019-11-08 20:10:31
供稿：网友
#include<iostream>#include<vector>using namespace std;vector<int> kkk;int N,M,K;int n;bool temp[1002];bool visited[1002];typedef struct ArcNode{ struct ArcNode *next; int adj;}ArcNode;//vector<ArcNode> arc;ArcNode arc[1000000];vector<ArcNode *> vexarc; typedef struct VNode{ int name; ArcNode *first;}VNode;typedef struct{ int arcnum,vexnum; VNode vs[1002];}LGraph;bool CreateLG(LGraph &G){ cin>>N>>M>>K; G.arcnum=M; G.vexnum=N; for(int t=0;t<G.vexnum;t++) { G.vs[t].name=t+1; G.vs[t].first=NULL; vexarc.push_back(G.vs[t].first); visited[t]=false; } for(int t=0;t<G.arcnum;t++) { int a,b; cin>>a>>b; arc[2*t].adj=a-1;arc[2*t].next=NULL; arc[2*t+1].adj=b-1;arc[2*t+1].next=NULL; // hu.adj=a-1;hu.next=NULL;arc.push_back(hu); // hu.adj=b-1;hu.next=NULL;arc.push_back(hu); if(G.vs[a-1].first==NULL) G.vs[a-1].first=vexarc[a-1]=&arc[2*t+1]; else vexarc[a-1]=vexarc[a-1]->next=&arc[2*t+1]; if(G.vs[b-1].first==NULL) G.vs[b-1].first=vexarc[b-1]=&arc[2*t]; else vexarc[b-1]=vexarc[b-1]->next=&arc[2*t]; } for(int t=0;t<K;t++) { int k; cin>>k; k--; kkk.push_back(k); //visited[k]=false; } return true;}bool bfs(LGraph &G,VNode f){ ArcNode *p=f.first; temp[f.name-1]=true; while(p!=NULL) { if(!temp[p->adj]) bfs(G,G.vs[p->adj]); p=p->next; } return true;}int main(){ LGraph G; CreateLG(G); for(vector<int>::iterator it=kkk.begin();it!=kkk.end();it++) { for(int t=0;t<G.vexnum;t++) temp[t]=visited[t]; temp[*it]=true; n=0; for(int t=0;t<G.vexnum;t++) {if(!temp[t]) {bfs(G,G.vs[t]);n++;}} if(n>0) cout<<n-1<<endl; else cout<<" "<<endl; } return 0;}
