Cod sursa(job #2169925)

Utilizator futurengineerOana Rosca futurengineer Data 14 martie 2018 19:21:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int n, m, x, y, comp;
bool viz[100001];
vector<int>v[100001], vt[100001], ctc[100001];
stack<int>st;

void dfs(int nod) {
  vector<int>::iterator i;
  viz[nod] = 1;
  for (i = v[nod].begin(); i < v[nod].end(); i++)
    if (!viz[*i])
      dfs(*i);
  st.push(nod);
}

void dfst(int nod) {
  vector<int>::iterator i;
  viz[nod] = 1;
  ctc[comp].push_back(nod);
  for (i = vt[nod].begin(); i < vt[nod].end(); i++)
    if (!viz[*i])
      dfst(*i);
}

int main () {
  ifstream fi("ctc.in");
  ofstream fo("ctc.out");
  fi >> n >> m;
  for (int i = 1; i <= m; i++) {
    fi >> x >> y;
    v[x].push_back(y);
    vt[y].push_back(x);
  }
  for (int i = 1; i <= n; i++)
    if (!viz[i])
      dfs(i);
  for (int i = 1; i <= n; i++)
    viz[i] = 0;
  while (!st.empty()) {
    int nodc = st.top(); st.pop();
    if (!viz[nodc])
      comp++, dfst(nodc);
  }
  fo << comp << '\n';
  vector<int>::iterator j;
  for (int i = 1; i <= comp; i++) {
    for (j = ctc[i].begin(); j < ctc[i].end(); j++)
      fo << *j << ' ';
    fo << '\n';
  }
  return 0;
}