fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define maxi 50002
  4. typedef long long int ll;
  5. using namespace std;
  6.  
  7. //int scan_d() {int ip=getchar_unlocked(),flag=1;int ret=0;for(;ip<'0'||ip>'9';ip=getchar_unlocked())if(ip=='-'){flag=-1;ip=getchar_unlocked();break;}for(;ip>='0'&&ip<='9';ip=getchar_unlocked())ret=ret*10+ip-'0';return flag*ret;}
  8.  
  9. bool visited[maxi]={false};
  10. vector<int>rooms[maxi];
  11. int win[maxi],I[maxi],id=-1;
  12. int root_id[maxi];
  13. ll counti=0,c,ans1;
  14.  
  15. void dfs(int v)
  16. {
  17.     int i,tmp;
  18.  
  19.     visited[v]=true;
  20.     I[v]=win[v];
  21.     root_id[v]=id;
  22.     for(i=0;i<rooms[v].size();i++)
  23.     {
  24.         tmp=rooms[v][i];
  25.         //cout<<v<<" "<<visited[v]<<"tmp="<<tmp<<" I[1] "<<I[1]<<endl;
  26.  
  27.         if(!visited[tmp])
  28.         {
  29.             dfs(tmp);
  30.             I[v]+=I[tmp];
  31.  
  32.         }
  33.     }
  34.      //cout<<v<<" I[v]="<<I[v]<<" I[1] "<<I[1]<<endl;
  35. }
  36. int main()
  37. {
  38.     int i,n,m,j;
  39.   cin>>n>>m;
  40.     for(i=1;i<=n;i++)
  41.         cin>>win[i];
  42.        for(i=0;i<m;i++)
  43.        {
  44.         int a,b;
  45.         cin>>a>>b;
  46.         rooms[a].pb(b);
  47.         rooms[b].pb(a);
  48.        }
  49.        for(i=1;i<=n;i++)
  50.        {
  51.  
  52.            if( !visited[i])
  53.            {
  54.                c=0;
  55.                id=i;
  56.                dfs(i);
  57.                 counti+=I[i]*(I[i]-1)/2;
  58.  
  59.            }
  60.  
  61.        } ans1=0;
  62.         for(i=1;i<=n;i++)
  63.         {
  64.  
  65.        // cout<<i<<" "<<root_id[i]<<" "<<I[i]<<endl;
  66.             if(I[i]>1)
  67.             {ans1++; continue;}
  68.             if(I[i]==1 && I[root_id[i]]>1 && i!=root_id[i])
  69.             {ans1++; continue;}
  70.             if(I[i]==0)
  71.                 continue;
  72.         }
  73.  
  74.        cout<<counti<<" "<<ans1<<endl;
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 4564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/q84hch
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!