Pagini recente » Cod sursa (job #659788) | Cod sursa (job #2861970) | Cod sursa (job #2975298) | Cod sursa (job #2070316) | Cod sursa (job #2926067)
/**
O metoda de a gasi CTC ale unui graf este
algoritmul lui Kosaraju care se bazeaza pe parcurgerile DFS
ale grafului G dat si ale lui G transpus (Gt).
In timpul parcurgerii lui G inseram varfurile vizitate
intr-o stiva. Parcurgand stiva, ne aventuram in Gt cu alte
DFS-uri, alipind la fiecare CTC varfurile parcurse din varful curent
al stivei in parcurgerea respectiva. Varfurile se elimina
din stiva inainte de a fi verificate drept canditat pentru radacina
arborelui construit de fiecare DFS in Gt.
*/
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int Nmax = 1e5 + 5;
vector<int> ans[Nmax], G[Nmax], Gt[Nmax];
stack<int> S;
bool seen[Nmax];
int ctc;
void dfs_1(int node)
{
seen[node] = 1;
for(auto i : G[node])
if(!seen[i])
dfs_1(i);
S.push(node);
}
void dfs_2(int node)
{
seen[node] = 1;
ans[ctc].push_back(node);
for(auto i : Gt[node])
if(!seen[i])
dfs_2(i);
}
int main()
{
int N, M;
in >> N >> M;
while(M--)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if(!seen[i])
dfs_1(i);
memset(seen, 0, sizeof(seen));
while(!S.empty())
{
int node = S.top();
S.pop();
if(!seen[node])
{
ctc++;
dfs_2(node);
}
}
out << ctc << '\n';
for(int i = 1; i <= ctc; ++i)
{
for(auto j : ans[i])
out << j << " ";
out << '\n';
}
return 0;
}