fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. vector<ll> adj[1000001];
  5. vector<ll> dfs_tree[1000001];
  6. ll parent[1000001];
  7. ll vis[1000001];
  8. ll vis1[1000001];
  9. ll disc[1000001];
  10. ll low[1000001];
  11. ll parent1[1000001];
  12. ll counts[1000001];
  13. ll counts2[1000001];
  14. ll P=1000000007;
  15. bool vis2[1000001],ap[1000001];
  16. ll disc1[1000001];
  17. ll low1[1000001];
  18. ll parent2[1000001];
  19. set<ll> articulations;
  20. set<ll> dhundo;
  21. ll visit[1000001];
  22.  ll times = 0;
  23.         set<pair<ll,ll>> se;
  24.         void bridges(ll src)
  25.         {
  26.             vis1[src]=1;
  27.             disc[src]=low[src]=++times;
  28.             for(ll i=0;i<adj[src].size();i++)
  29.             {
  30.                 ll v=adj[src][i];
  31.                 if(!vis1[v])
  32.                 {
  33.                     parent1[v]=src;
  34.                     bridges(v);
  35.                     low[src]=min(low[v],low[src]);
  36.                     if (low[v] > disc[src])
  37.                     {
  38.                         if(se.find({v,src})!=se.end()||se.find({src,v})!=se.end())
  39.                         {
  40.  
  41.                         }
  42.                         else 
  43.                         {
  44.                            // cout<<src<<" "<<v<<endl;
  45.                             se.insert({src,v});
  46.                         }
  47.                     } 
  48.                 }
  49.                 else if(v!=parent1[src])
  50.                 {
  51.                      low[src]=min(low[src], disc[v]); 
  52.                 }
  53.             }
  54.         }
  55.         void cheti_chand_dfs(ll src)
  56.         {
  57.             if(!vis[src])
  58.             {
  59.             vis[src]=1;
  60.             for(ll i=0;i<adj[src].size();i++)
  61.             {
  62.                 if(!vis[adj[src][i]])
  63.                 {
  64.                     parent[adj[src][i]]=src;
  65.                     dfs_tree[adj[src][i]].push_back(src);
  66.                     dfs_tree[src].push_back(adj[src][i]);
  67.                     cheti_chand_dfs(adj[src][i]);
  68.                 }
  69.             }
  70.             }
  71.         }
  72.         void dfs(ll src)
  73.         {
  74.             if(!visit[src])
  75.             {
  76.             visit[src]=1;
  77.             for(ll i=0;i<adj[src].size();i++)
  78.             {
  79.                 if(!visit[adj[src][i]])
  80.                 {
  81.                     dfs(adj[src][i]);
  82.                 }
  83.             }
  84.             }
  85.         }
  86.         void count_nodes(ll src,ll e)
  87.         {
  88.             if(dhundo.find(src)!=dhundo.end())
  89.             counts[src]=1;
  90.             else 
  91.             counts[src]=0;
  92.             counts2[src]=1;
  93.             for(ll i=0;i<dfs_tree[src].size();i++)
  94.             {
  95.                 ll v=dfs_tree[src][i];
  96.                 if(v==e)
  97.                 {
  98.                     continue;
  99.                 }
  100.                 count_nodes(v,src);
  101.                counts[src]+=counts[v];
  102.                counts2[src]+=counts2[v];
  103.             }
  104.         }  
  105.  
  106.  void artic(ll u)
  107.  {
  108.     ll children = 0; 
  109.     vis2[u] = true; 
  110.     disc1[u] = low1[u] = ++times; 
  111.     for (ll i =0; i<adj[u].size();++i) 
  112.     { 
  113.         ll v = adj[u][i];
  114.         if (!vis2[v]) 
  115.         { 
  116.             children++; 
  117.             parent2[v] = u; 
  118.             artic(v); 
  119.             low1[u]  = min(low1[u], low1[v]); 
  120.             if (parent2[u] == 0 && children > 1)
  121.             {
  122.                ap[u] = true;
  123.                articulations.insert(u); 
  124.             } 
  125.             if (parent2[u] != 0 && low1[v] >= disc1[u]) 
  126.             {
  127.                  ap[u] = true; 
  128.                 articulations.insert(u);
  129.             } 
  130.         } 
  131.         else if (v != parent2[u]) 
  132.             low1[u]  = min(low1[u], disc1[v]); 
  133.     } 
  134.  }
  135.         int main()
  136.         {
  137.             ll i,j,k,l,m,n,o,p,q,r,s,t,x;
  138.             cin>>t;
  139.             while(t--)
  140.             {
  141.             cin>>n>>m>>x;
  142.             memset(vis,0,sizeof(ll)*(n+1));
  143.             memset(vis1,0,sizeof(ll)*(n+1));
  144.             memset(low,0,sizeof(ll)*(n+1));
  145.             memset(disc,0,sizeof(ll)*(n+1));
  146.             memset(parent,0,sizeof(ll)*(n+1));
  147.             memset(parent1,0,sizeof(ll)*(n+1));
  148.             memset(counts,0,sizeof(ll)*(n+1));
  149.             memset(vis2,false,sizeof(bool)*(n+1));
  150.             memset(parent2,0,sizeof(ll)*(n+1));
  151.             memset(disc1,0,sizeof(ll)*(n+1));
  152.             memset(low1,0,sizeof(ll)*(n+1));
  153.             memset(ap,false,sizeof(bool)*(n+1));
  154.             memset(counts2,0,sizeof(ll)*(n+1));
  155.             dhundo.clear();
  156.             se.clear();
  157.             articulations.clear();
  158.              for(i=1;i<=n;i++)
  159.              {
  160.                  adj[i].clear();
  161.                  dfs_tree[i].clear();
  162.              }
  163.             for(i=0;i<x;i++)
  164.             {
  165.                 cin>>j;
  166.                 dhundo.insert(j);
  167.             }
  168.             for(i=0;i<m;i++)
  169.             {
  170.                 cin>>j>>k;
  171.                 adj[j].push_back(k);
  172.                 adj[k].push_back(j);
  173.             } 
  174.  
  175.  
  176.  
  177.             // if x is less than 100 applying dsu;
  178.              if(dhundo.size()==n)
  179.              {
  180.                  cout<<0<<" "<<1<<"\n";
  181.                  continue;
  182.              }
  183.             ll ma=0;
  184.            ll point=*(dhundo.begin());
  185.            if(n<=501)
  186.            {
  187.                for(auto it:dhundo)
  188.             {
  189.                 memset(visit,0,sizeof(ll)*(n+1));
  190.                 visit[it]=true;
  191.                 for(i=1;i<=n;i++)
  192.                 {
  193.                    if(dhundo.find(i)!=dhundo.end())
  194.                    {
  195.                        if(!visit[i])
  196.                        {
  197.                            dfs(i);
  198.                        }
  199.                    }
  200.                 }
  201.                 ll xxx=0;
  202.                 for(i=1;i<=n;i++)
  203.                 {
  204.                     if(!visit[i])
  205.                     xxx++;
  206.                 }
  207.                 if(xxx>ma)
  208.                 {
  209.                     ma=xxx;
  210.                     point=it;
  211.                 }
  212.             }
  213.             cout<<ma<<" "<<point<<"\n";
  214.           //  continue;
  215.            }
  216.  
  217.  
  218.             times=0;
  219.             cheti_chand_dfs(1);
  220.             times=0;
  221.             bridges(1);
  222.           times=0;
  223.             count_nodes(1,0);
  224.           times=0;
  225.            artic(1);
  226.              times=0;
  227.  
  228.            for(i=1;i<=n;i++)
  229.            {
  230.  
  231.                if(dhundo.find(i)!=dhundo.end())
  232.                {
  233.                    if(1)
  234.                    {
  235.                        ll xx=0,yy=0;
  236.                        ll zz=0,term=0;
  237.                        ll flag=1;
  238.     if(se.find({parent1[i],i})!=se.end()||se.find({i,parent1[i]})!=se.end())
  239.     {
  240.         term=1;
  241.         if(counts[1]==counts[i])
  242.         {
  243.             zz+=counts2[1]-counts2[i];
  244.         }
  245.     }
  246.                        if(counts[1]==counts[i])
  247.                        {
  248.                            xx=counts2[1]-counts2[i];
  249.                        }
  250.                        else 
  251.                        {
  252.                           flag=0;
  253.                        }
  254.                        for(j=0;j<dfs_tree[i].size();j++)
  255.                        {
  256. if(se.find({i,dfs_tree[i][j]})!=se.end()||se.find({dfs_tree[i][j],i})!=se.end()||term==1)
  257.         {
  258.             if(dfs_tree[i][j]!=parent1[i])
  259.             {
  260.                 if(counts[dfs_tree[i][j]]==0)
  261.                 {
  262.                     yy+=counts2[dfs_tree[i][j]];
  263.                 }
  264.             }
  265.             else 
  266.             {
  267.  
  268.             }
  269.        }
  270.              else
  271.              {
  272.              if(dfs_tree[i][j]!=parent1[i])
  273.              {
  274.                 if(counts[dfs_tree[i][j]]==0)
  275.                 {
  276.                     if(term==0)
  277.                     xx+=counts2[dfs_tree[i][j]];
  278.                 }
  279.                 else
  280.                 {
  281.                     if(term==0)
  282.                     flag=0;
  283.                 }
  284.              }
  285.             }     
  286.                        }
  287.                         if(zz+yy>ma)
  288.                         {
  289.                             ma=zz+yy;
  290.                             point=i;
  291.                         }
  292.                        if(flag==1)
  293.                        {
  294.                            yy+=xx;
  295.                        }
  296.                         if(ma<yy)
  297.                         {
  298.                             ma=yy;
  299.                             point=i;
  300.                         }
  301.  
  302.                    }
  303.                }
  304.            }
  305.             cout<<ma<<" "<<point<<endl;
  306.             }
  307.             return 0;
  308.         }
  309.  
Success #stdin #stdout 0.02s 50544KB
comments (?)
stdin
copy 
1
4 5 3
3 2 1
1 2
2 3
3 4
4 1
2 4
stdout
copy 
0 1
0 1
https://ideone.com/PbSfKy
language:
C++14 (gcc 8.3)
created:
4 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!