Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- map<int, vector<int> >adj;
- map<int, int>visited;
- map<int,int>::iterator it;
- int cnt1,cnt2;
- void bfs(int s)
- {
- queue<int>q;
- q.push(s);
- visited[s]=1;
- while(!q.empty())
- {
- int u=q.front();
- //cout<<u<<" ";
- q.pop();
- for(int i=0 ; i< adj[u].size() ; i++ )
- {
- if(visited[adj[u][i]]==0)
- {
- if(visited[u]==2)
- {
- int v=adj[u][i];
- // cout<<u<<endl;
- visited[v]=1;
- q.push(v);
- }
- else if(visited[u]==1)
- {
- int v=adj[u][i];
- visited[v]=2;
- q.push(v);
- }
- }
- }
- }
- }
- int main()
- {
- int t,cs=1;
- cin>>t;
- while(t--)
- {
- int n,edge,n1,n2,cnn1=0,cnt2=0;
- visited.clear();
- cin>>edge;
- vector<int>s;
- s.clear();
- int p;
- for(int i=1; i<=edge; i++)
- {
- cin>>n1>>n2;
- s.push_back(n1);
- s.push_back(n2);
- adj[n1].push_back(n2);
- adj[n2].push_back(n1);
- p=n1;
- }
- bfs(p);
- printf("Case %d: ",cs++);
- for(int i=0; i<s.size(); i++)
- {
- if(visited[s[i]]==0)
- {
- bfs(s[i]);
- }
- }
- for(it=visited.begin() ; it!=visited.end() ; it++ )
- {
- // cout<<it->first<<" "<<it->second<<endl;
- if(it->second==1)
- {
- cnt1++;
- }
- else if(it->second==2)
- {
- cnt2++;
- }
- }
- cout<<max(cnt1,cnt2)<<endl;
- cnt1=0;
- cnt2=0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement