Pagini recente » Cod sursa (job #363923) | Cod sursa (job #3145259) | Cod sursa (job #2058497) | Cod sursa (job #993161) | Cod sursa (job #1936727)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
stack<int> S;
vector<int> G[100001];
int N,M,ID = 0;
int low[100001],id[100001];
vector< vector<int> > SCC;
bool in_stack[100001];
void tarjan(int node)
{
low[node] = ++ID;
id[node] = ID;
S.push(node); in_stack[node] = 1;
for (auto u: G[node])
{
if (id[u] == 0)
{
tarjan(u);
low[node] = min(low[node],low[u]);
}
else if (in_stack[u])
low[node] = min(low[node],low[u]);
}
if (low[node] == id[node])
{
SCC.push_back(vector<int>());
int v;
do {
v = S.top(); S.pop();
SCC.back().push_back(v);
in_stack[v] = 0;
} while (v != node);
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
for (int i = 1; i <= M; i++)
{
int a,b; fin >> a >> b;
G[a].push_back(b);
}
for (int i = 1; i <= N; i++)
if (id[i] == 0)
tarjan(i);
fout << SCC.size() << "\n";
for (auto v: SCC) {
for (auto u: v)
fout << u << " ";
fout << "\n";
}
}