Pagini recente » Cod sursa (job #1513509) | Cod sursa (job #3178682) | Cod sursa (job #2038078) | Cod sursa (job #716384) | Cod sursa (job #1708854)
//Kosaraju O (n + m)
//se face o sortare topologica pe graful a reprezentatnilor COMPONENTELOR TARE CONEXE care e un dag
//se parcurge dintr-un nod in a carui componenta tare conexa nu intra nimic pe graful normal,
//pe graful transpus, orice nod care e atins face parte din respectiva componenta tare conexa
// (pentru ca daca plec din nodul x, pot ajunge in oricare alt nod y =>x -> y, datorita
//soratrii topologice, daca din nodul x merg pe graful transpus si ajung la y, insemna ca pe graful
//normal din y pot ajunge in x => x si y in aceeasi componenta tare conexa.
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100009;
int n; int m;
vector<int> g[NMAX];
vector< vector<int> > ctc; int cnt;
int viz[NMAX];
int s[NMAX];
int low[NMAX];
int discovery;
int ins[NMAX];
int ind[NMAX];
void read() {
fin >> n >> m;
for(int i = 1; i <= m ; ++i) {
int x; int y;
fin >> x >> y;
g[x].push_back(y);
}
}
void tarjan(int node) {
viz[node] = 1;
++discovery;
ind[node] = discovery;//punctul de descoperire
low[node] = discovery;//cat de sus putem ajunge de la nodul x
s[++s[0]] = node;//bag nodul pe stiva
ins[node] = 1;
for(int x : g[node])
if(viz[x] == 0) {
tarjan(x);
low[node] = min(low[node], low[x]);
} else if(ins[x] == 1) //a fost vizitat si a ramas in stiva, daca nu ar fi fost in stiva
//ar fi insemnat ca sigur e din alta componenta tare conexa
low[node] = min(low[node], low[x]);
if(low[node] == ind[node]) { //niciun nod din subarborele ramad al lui node
//nu are un alt drum in sus peste nodul node =>
ctc.push_back(vector<int>(0));
int x;
do {
ins[ s[s[0]] ] = 0;
ctc[cnt].push_back( (x = s[s[0]]) );
s[0]--;
} while(node != x);
cnt++;
}
}
void solve() {
for(int i = 1; i <= n; ++i)
if(viz[i] == 0)
tarjan(i);
fout << cnt << '\n';
for(int i = 0 ; i < cnt; ++i) {
for(int x : ctc[i])
fout << x << ' ';
fout << '\n';
}
}
int main() {
read(); solve();
return 0;
}