Pagini recente » Cod sursa (job #706776) | Cod sursa (job #2036849) | Cod sursa (job #1763757) | Cod sursa (job #1387232) | Cod sursa (job #2940191)
/// Tarjan
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, st[100005], top, scc, nr;
vector <int> a[100005], ctc[100005];
int lowlink[100005], id[100005];
bitset <100005> onStack, viz;
void Dfs(int x)
{
//cout << x << " ";
viz[x] = 1;
st[++top] = x;
onStack[x] = 1;
id[x] = lowlink[x] = ++nr;
for (auto w : a[x])
{
if (viz[w] == 0)
Dfs(w);
if (onStack[w] == 1) lowlink[x] = min(lowlink[w], lowlink[x]);
}
if (id[x] == lowlink[x])
{
scc++;
while (top > 0 and st[top] != x)
{
ctc[scc].push_back(st[top]);
onStack[st[top]] = 0;
lowlink[st[top]] = x;
top--;
}
ctc[scc].push_back(x);
top--;
}
}
void Test_Case()
{
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 (viz[i] == 0)
Dfs(i);
fout << scc << "\n";
for (i = 1; i <= scc; i++)
{
for (auto j : ctc[i])
fout << j << " ";
fout << "\n";
}
}
int main()
{
int t;
ios_base::sync_with_stdio(false);
cin.tie(0);
t = 1;
while (t--)
Test_Case();
return 0;
}