Guest User

Untitled

a guest
Mar 14th, 2020
2,006
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> v[100005],s;
  4. int sq,dep[100005];
  5. bool marked[100005];
  6. void dfs(int node)
  7. {
  8.     s.push_back(node);
  9.     dep[node]=s.size();
  10.     for (int u:v[node])
  11.     {
  12.         if (!dep[u])
  13.         dfs(u);
  14.         else if (dep[node]-dep[u]+1>=sq)
  15.         {
  16.             printf("2\n%d\n",dep[node]-dep[u]+1);
  17.             for (int i=dep[u]-1;i<dep[node];i++)
  18.             printf("%d ",s[i]);
  19.             exit(0);
  20.         }
  21.     }
  22.     if (!marked[node])
  23.     {
  24.         for (int u:v[node])
  25.         marked[u]=1;
  26.     }
  27.     s.pop_back();
  28. }
  29. int main()
  30. {
  31.     int n,m;
  32.     scanf("%d%d",&n,&m);
  33.     while (sq*sq<n)
  34.     sq++;
  35.     while (m--)
  36.     {
  37.         int a,b;
  38.         scanf("%d%d",&a,&b);
  39.         v[a].push_back(b);
  40.         v[b].push_back(a);
  41.     }
  42.     dfs(1);
  43.     printf("1\n");
  44.     for (int i=1;sq;i++)
  45.     {
  46.         if (!marked[i])
  47.         {
  48.             printf("%d ",i);
  49.             sq--;
  50.         }
  51.     }
  52. }
Add Comment
Please, Sign In to add comment