Pagini recente » Cod sursa (job #217161) | Cod sursa (job #1611617) | Cod sursa (job #1641798) | Cod sursa (job #937542) | Cod sursa (job #2940231)
/// Tarjan
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> a[100005], scc[100005];
int n, m, st[100005], top, id[100005], lowlink[100005], nr, nrscc;
bitset <100005> onStack;
void Dfs(int x)
{
st[++top] = x;
onStack[x] = 1;
id[x] = lowlink[x] = ++nr;
for (auto w : a[x])
{
if (id[w] == 0)
Dfs(w);
if (onStack[w]) lowlink[x] = min(lowlink[w], lowlink[x]);
}
if (id[x] == lowlink[x])
{
nrscc++;
scc[nrscc].push_back(x);
while (top and st[top] != x)
{
scc[nrscc].push_back(st[top]);
onStack[st[top]] = 0;
lowlink[st[top]] = lowlink[x];
top--;
}
onStack[st[top]] = 0;
lowlink[st[top]] = lowlink[x];
top--;
}
}
int main()
{
int i, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
a[x].push_back(y);
}
for (i = 1; i <= n; i++)
if (id[i] == 0)
Dfs(i);
fout << nrscc << "\n";
for (i = 1; i <= nrscc; i++)
{
for (auto j : scc[i])
fout << j << " ";
fout << "\n";
}
return 0;
}