CompetitiveProgramming/codeforces/100962/K.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

int n, cnt, low[500500], num[500500], par[500500], numChild[500500], flag[500500];
vector <int> a[500500];
set <int> cut;

void visit(int x)
{
  num[x] = low[x] = ++cnt;
  numChild[par[x]]++;
  for (int y : a[x])
    if (y != par[x])
    {
      if (num[y]) low[x] = min(low[x], num[y]);
      else
      {
        par[y] = x;
        visit(y);
        low[x] = min(low[x], low[y]);
      }
    }
}

void dfs(int x, int par, int bad)
{
  if (flag[x]++)
  {
    cout << 0 << endl;
    exit(0);
  }

  for (int y : a[x])
    if (y != bad && y != par)
      dfs(y, x, bad);
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int x, y, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++)
  {
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }

  for (int i = 1; i <= n; i++)
    if (a[i].size() % 2)
    {
      cout << 0 << endl;
      return 0;
    }

  visit(1);
  for (int i = 1; i <= n; i++)
    if (par[i] && low[i] >= num[par[i]] && (par[par[i]] || numChild[par[i]] >= 2))
      cut.insert(par[i]);

  if (cut.size() >= 2)
  {
    cout << 0 << endl;
    return 0;
  }

  if (cut.size() == 1)
  {
    int bad = *cut.begin();
    for (int i = 1; i <= n; i++)
      if (i != bad && !flag[i])
        dfs(i, 0, bad);
    cout << 1 << endl << bad << endl;
    return 0;
  }

  vector <int> ans;
  for (int i = 1; i <= n; i++)
    if (a[i].size() + n - 2 == m)
      ans.push_back(i);

  cout << ans.size() << endl;
  for (int x : ans)
    cout << x << ' ';
}