mohammedehab2002

Untitled

Jun 13th, 2020
4,417
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int pos[100005];
  4. vector<int> v[100005],col[100005],s;
  5. vector<int> cyc;
  6. bool dfs(int node)
  7. {
  8.     pos[node]=s.size();
  9.     col[pos[node]%2].push_back(node);
  10.     s.push_back(node);
  11.     int low=-1;
  12.     for (int u:v[node])
  13.     {
  14.         if (pos[u]!=-1 && pos[node]-pos[u]>1)
  15.         low=max(low,pos[u]);
  16.     }
  17.     if (low!=-1)
  18.     {
  19.         for (int i=low;i<=pos[node];i++)
  20.         cyc.push_back(s[i]);
  21.         return 1;
  22.     }
  23.     for (int u:v[node])
  24.     {
  25.         if (pos[u]==-1)
  26.         {
  27.             if (dfs(u))
  28.             return 1;
  29.         }
  30.     }
  31.     s.pop_back();
  32.     return 0;
  33. }
  34. int main()
  35. {
  36.     int n,m,k;
  37.     scanf("%d%d%d",&n,&m,&k);
  38.     while (m--)
  39.     {
  40.         int a,b;
  41.         scanf("%d%d",&a,&b);
  42.         v[a].push_back(b);
  43.         v[b].push_back(a);
  44.     }
  45.     memset(pos,-1,sizeof(pos));
  46.     dfs(1);
  47.     if (cyc.empty())
  48.     {
  49.         if (col[0].size()<col[1].size())
  50.         swap(col[0],col[1]);
  51.         printf("1\n");
  52.         for (int i=0;i<(k+1)/2;i++)
  53.         printf("%d ",col[0][i]);
  54.     }
  55.     else
  56.     {
  57.         if (cyc.size()<=k)
  58.         {
  59.             printf("2\n%d\n",cyc.size());
  60.             for (int i:cyc)
  61.             printf("%d ",i);
  62.         }
  63.         else
  64.         {
  65.             printf("1\n");
  66.             for (int i=0;i<(k+1)/2;i++)
  67.             printf("%d ",cyc[2*i]);
  68.         }
  69.     }
  70. }
RAW Paste Data