Cod sursa(job #2211980)

Utilizator PetyAlexandru Peticaru Pety Data 12 iunie 2018 17:53:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

bool viz[100002];
int n, m, x, y, nr;

vector<int>v1[100002];
vector<int>v2[100002];
vector<int>sol[100002];
stack<int>st;

void dfs (int x) {
  viz[x] = 1;
  for (int i = 0; i < v1[x].size(); i++) {
    if (!viz[v1[x][i]])
      dfs(v1[x][i]);
  }
  st.push(x);
}

void dfs2 (int x) {
  viz[x] = 1;
  for (int i = 0; i < v2[x].size(); i++) {
    if (!viz[v2[x][i]])
      dfs2(v2[x][i]);
  }
  sol[nr].push_back(x);
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y;
    v1[x].push_back(y);
    v2[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    if (viz[i] == 0)
      dfs(i);
  }
  memset(viz, 0, sizeof(viz));
  while (!st.empty()) {
    if (viz[st.top()] == 0) {
      nr++;
      dfs2(st.top());
    }
    st.pop();
  }
  fout << nr << "\n";
  for (int i = 1; i <= nr; i++) {
    for (int j = 0; j < sol[i].size(); j++)
      fout << sol[i][j] << " ";
    fout << "\n";
  }
  return 0;
}