Pagini recente » Cod sursa (job #2362892) | Autentificare | Cod sursa (job #117043) | Cod sursa (job #2015200) | Cod sursa (job #2232046)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#define MAXN 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int>graf[MAXN],graf_transpus[MAXN],scc[MAXN];
stack<int>stiva;
bool viz[MAXN];
int n,m,cnt;
void dfs(int start){
viz[start] = true;
for(auto i : graf[start])
if(!viz[i])
dfs(i);
stiva.push(start);
}
void dfs_reverse(int start){
viz[start] = true;
cout<<start<<" ";
scc[cnt].push_back(start);
for(auto i : graf_transpus[start])
if(!viz[i])
dfs_reverse(i);
}
void Kosaraju(){
for(int i = 1; i <= n; i++)
viz[i] = false;
while(!stiva.empty()){
int nod = stiva.top();
stiva.pop();
if(!viz[nod]){
dfs_reverse(nod);
cnt++;
}
}
}
int main()
{
in>>n>>m;
for(int i = 1; i <= m; i++){
int x,y;
in>>x>>y;
graf[x].push_back(y);
graf_transpus[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs(i);
Kosaraju();
out<<cnt<<"\n";
for(int i = 0; i < cnt; i++){
for(int j = 0; j < scc[i].size(); j++)
out<<scc[i][j]<<" ";
out<<"\n";
}
return 0;
}