Cod sursa(job #2203005)

Utilizator mulilisimomoisescu mihai mulilisimo Data 10 mai 2018 18:00:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin ("ctc.in");
ofstream cout ("ctc.out");

const int nmax = 100000;

int n, m;
int x, y;
int ctc;

bool viz[1 + nmax];
int comp[1 + nmax];
stack <int> st;
vector <int> g[1 + nmax], gr[1 + nmax], nodes[1 + nmax];

void dfsPlus(int nod) {
  viz[nod] = 1;
  for(int i = 0; i < g[nod].size(); i++)
    if(!viz[g[nod][i]])
      dfsPlus(g[nod][i]);
  st.push(nod);
}

void dfsMinus(int nod, int index_ctc) {
  comp[nod] = index_ctc;
  for(int i = 0; i < gr[nod].size(); i++)
    if(comp[gr[nod][i]] == -1)
      dfsMinus(gr[nod][i], index_ctc);
}

int main() {
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    gr[y].push_back(x);
  }
  for(int i = 1; i <= n; i++) {
    if(!viz[i])
      dfsPlus(i);
  }
  int nod;
  for(int i = 1; i <= n; i++)
    comp[i] = -1;
  while(!st.empty()) {
    nod = st.top();
    st.pop();
    if(comp[nod] == -1) {
      ctc++;
      dfsMinus(nod, ctc);
    }
  }
  for(int i = 1; i <= n; i++)
    nodes[comp[i]].push_back(i);
  cout << ctc << "\n";
  for(int i = 1; i <= ctc; i++) {
    for(int j = 0; j < nodes[i].size(); j++)
      cout << nodes[i][j] << " ";
    cout << "\n";
  }
  return 0;
}