Pagini recente » Cod sursa (job #593709) | Cod sursa (job #1288010) | Cod sursa (job #2728564) | Cod sursa (job #3261645) | Cod sursa (job #3124945)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[100001];
vector<int>GT[100001];
vector<int>S;
vector<int>V(100001, false);
vector<int>VT(100001, false);
vector<int>conexe[100001];
int n, m, maxx, cnt;
void citire() {
f >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void dfs(int node) {
V[node] = true;
for(auto i : G[node]) {
if(!V[i]) dfs(i);
}
S.push_back(node);
}
void dfs1(int node) {
VT[node] = true;
conexe[cnt].push_back(node);
for(auto i : GT[node]) {
if(!VT[i]) dfs1(i);
}
}
void kosaraju() {
for(int i = 1; i <= n; i++) {
if(!V[i]) dfs(i);
}
for(vector<int>::reverse_iterator it = S.rbegin(); it != S.rend(); it++) {
if(!VT[*it]) {
cnt++;
dfs1(*it);
}
}
}
void afisare() {
g << cnt << '\n';
for(int i = 1; i <= cnt; i++) {
for(auto j : conexe[i]) {
g << j << ' ';
}
g << '\n';
}
}
int main() {
citire();
kosaraju();
afisare();
}