Pagini recente » Cod sursa (job #2113182) | Cod sursa (job #1867969) | Cod sursa (job #761106) | Cod sursa (job #2286304) | Cod sursa (job #3336640)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 5;
const char nl = '\n';
vector<int> g[NMAX], invers[NMAX], componente[NMAX];
stack<int> order;
int visitat[NMAX];
void dfs(int nod) {
visitat[nod] = 1;
for (auto neigh: invers[nod]) {
if (visitat[neigh] == 0) {
dfs(neigh);
}
}
order.push(nod);
}
void dfs2(int nod, int nivel) {
visitat[nod] = 1;
for (auto neigh: g[nod]) {
if (visitat[neigh] == 0) {
dfs2(neigh, nivel);
}
}
componente[nivel].push_back(nod);
}
int main () {
int n, m, x, y;
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> x >> y;
g[x].push_back(y);
invers[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
visitat[i] = 0;
}
for (int i = 1; i <= n; i++) {
if (visitat[i] == 0) {
dfs(i);
}
}
for (int i = 1; i <= n; i++) {
visitat[i] = 0;
}
int nivel = -1;
while (!order.empty()) {
int nod = order.top();
order.pop();
if (visitat[nod] == 0) {
nivel++;
dfs2(nod, nivel);
}
}
fout << ++nivel << nl;
for (auto it: componente) {
for (auto nod: it) {
fout << nod << " ";
}
fout << nl;
}
}