Pagini recente » Cod sursa (job #575969) | Cod sursa (job #413171) | Borderou de evaluare (job #1776543) | Cod sursa (job #1741203) | Cod sursa (job #2790323)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, ctcNr;
bool fr[100100], frTrans[100100];
vector<int> adj[100100], adjTrans[100100], ctc[100100];
stack<int> s;
void dfs(int node)
{
fr[node] = 1;
for(auto it: adj[node])
if(!fr[it])
dfs(it);
s.push(node);
}
void dfsTrans(int node)
{
ctc[ctcNr].push_back(node);
frTrans[node] = 1;
for(auto it: adjTrans[node])
if(!frTrans[it])
dfsTrans(it);
}
void kosaraju()
{
for(int i = 1; i <= n; i++)
if(!fr[i])
dfs(i);
while(!s.empty())
{
int node = s.top();
if(!frTrans[node])
{
ctcNr++;
dfsTrans(node);
}
s.pop();
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
adj[x].push_back(y);
adjTrans[y].push_back(x);
}
kosaraju();
out << ctcNr << '\n';
for(int i = 1; i <= ctcNr; i++)
{
for(auto it: ctc[i])
out << it << ' ';
out << '\n';
}
return 0;
}