Guest User

Untitled

a guest
Mar 14th, 2020
1,359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. set<pair<int,int> > s;
  4. vector<int> v[100005];
  5. bool del[100005];
  6. int deg[100005],occ[100005];
  7. void remove(int node)
  8. {
  9.     if (del[node])
  10.     return;
  11.     s.erase({deg[node],node});
  12.     del[node]=1;
  13.     for (int u:v[node])
  14.     {
  15.         if (!del[u])
  16.         {
  17.             s.erase({deg[u],u});
  18.             deg[u]--;
  19.             s.insert({deg[u],u});
  20.         }
  21.     }
  22. }
  23. int main()
  24. {
  25.     int n,m,sq=1;
  26.     scanf("%d%d",&n,&m);
  27.     while (sq*sq<n)
  28.     sq++;
  29.     while (m--)
  30.     {
  31.         int a,b;
  32.         scanf("%d%d",&a,&b);
  33.         v[a].push_back(b);
  34.         v[b].push_back(a);
  35.         deg[a]++;
  36.         deg[b]++;
  37.     }
  38.     for (int i=1;i<=n;i++)
  39.     s.insert({deg[i],i});
  40.     vector<int> ans;
  41.     while (!s.empty())
  42.     {
  43.         auto p=*s.begin();
  44.         s.erase(s.begin());
  45.         if (p.first+1>=sq)
  46.         {
  47.             printf("2\n");
  48.             vector<int> d({p.second});
  49.             occ[p.second]=1;
  50.             while (1)
  51.             {
  52.                 pair<int,int> nex(1e9,0);
  53.                 for (int u:v[d.back()])
  54.                 {
  55.                     if (!del[u])
  56.                     nex=min(nex,make_pair(occ[u],u));
  57.                 }
  58.                 if (nex.first)
  59.                 {
  60.                     printf("%d\n",(int)d.size()-nex.first+1);
  61.                     for (int i=nex.first-1;i<d.size();i++)
  62.                     printf("%d ",d[i]);
  63.                     return 0;
  64.                 }
  65.                 d.push_back(nex.second);
  66.                 occ[nex.second]=d.size();
  67.             }
  68.         }
  69.         ans.push_back(p.second);
  70.         remove(p.second);
  71.         for (int u:v[p.second])
  72.         remove(u);
  73.     }
  74.     printf("1\n");
  75.     for (int i=0;i<sq;i++)
  76.     printf("%d ",ans[i]);
  77. }
Add Comment
Please, Sign In to add comment