[Codeforces] E. Fairy

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Fairy
Source            : Codeforces
Category          : Graph Theory
Algorithm         : DFS Tree 
Tutorial          : https://codeforces.com/blog/entry/68138 
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll                 long long int  
#define endl              '\n'  
  
static const int maxn = 1e5 + 5;  
  
struct Node  
{  
      int v, id;  
      Node(int v = 0, int id = 0)  
            : v(v), id(id) {}  
};  
  
vector < vector <Node> > graph;  
int color[maxn];  
int contradictory[maxn];  
int contradictoryEdges;  
bool vis[maxn];  
int in[maxn];  
int dfsTime;  
bool isBipartite;  
  
void dfs(int u = 1, int p = -1, int c = 0)  
{  
      in[u] = ++dfsTime;  
      color[u] = c;  
      vis[u] = 1;  
      for (Node it : graph[u])  
      {  
            int v = it.v;  
            int id = it.id;  
            if (v == p) continue;  
            if (vis[v] == 0)  
            {  
                  dfs(v, u, c ^ 1);  
            }  
            else if (in[v] < in[u])  
            {  
                  if (color[u] == color[v]) isBipartite = false, contradictory[id] = 1;  
                  else contradictory[id] = 2;  
            }  
      }  
}  
  
int dp1[maxn];  
int dp2[maxn];  
bool used[maxn];  
  
void solve(int u, int p = -1)  
{  
      used[u] = 1;  
      for (Node it : graph[u])  
      {  
            int v = it.v;  
            int id = it.id;  
            if (v == p) continue;  
            if (used[v] == 0)  
            {  
                  solve(v, u);  
                  dp1[u] += dp1[v];  
                  dp2[u] += dp2[v];  
            }  
            else if (in[v] < in[u])  
            {  
                  if (contradictory[id] == 1) dp1[u]++, dp1[v]--;  
                  else if (contradictory[id] == 2) dp2[u]++, dp2[v]--;  
            }  
      }  
}  
  
vector <int> ans;  
bool visited[maxn];  
  
void solution(int u, int p = - 1)  
{  
      visited[u] = 1;  
      for (Node it : graph[u])  
      {  
            int v = it.v;  
            int id = it.id;  
            if (v == p) continue;  
            if (visited[v] == 0)  
            {  
                  if (dp1[v] == contradictoryEdges and dp2[v] == 0)  
                  {  
                        ans.push_back(id);  
                  }  
                  solution(v, u);  
            }  
      }  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      int tnode, tedge;  
      cin >> tnode >> tedge;  
      graph.resize(tnode + 1);  
      for (int e = 1; e <= tedge; e++)  
      {  
            int u, v;  
            cin >> u >> v;  
            graph[u].emplace_back(v, e);  
            graph[v].emplace_back(u, e);  
      }  
      int nonBipartiteComponent = 0;  
      for (int i = 1; i <= tnode; i++)  
      {  
            if (vis[i] == 0)  
            {  
                  isBipartite = true;  
                  dfs(i);  
                  if (isBipartite == false) ++nonBipartiteComponent;  
            }  
      }  
      if (nonBipartiteComponent == 0)  
      {  
            cout << tedge << endl;  
            for (int i = 1; i <= tedge; i++) cout << i << " \n"[i == tedge];  
            return 0;  
      }  
      if (nonBipartiteComponent > 2)  
      {  
            cout << 0 << endl;  
            return 0;  
      }  
      for (int i = 1; i <= tedge; i++) contradictoryEdges += contradictory[i] == 1;  
      for (int i = 1; i <= tnode; i++) if (used[i] == 0) solve(i);  
      for (int i = 1; i <= tnode; i++) if (visited[i] == 0) solution(i);  
      if (contradictoryEdges == 1) for (int i = 1; i <= tedge; i++) if (contradictory[i] == 1) ans.push_back(i);  
      cout << ans.size() << endl;  
      sort(ans.begin(), ans.end());  
      for (int x : ans) cout << x << " ";  
}