Pagini recente » Cod sursa (job #2904165) | Cod sursa (job #1763438) | Cod sursa (job #4818) | Cod sursa (job #1421156) | Cod sursa (job #2951247)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> a[100005], ctc[100005];
int n , m, id[100005], st[100005], top;
int onStack[100005], lowlink[100005], nr;
int nrctc; /// nr de componentele tari conexe
/// ctc[] - componentele tari conexe
void DFS_Tarj(int x)
{
st[++top] = x;
onStack[x] = 1;
id[x] = lowlink[x] = ++nr;
for(auto w : a[x])
{
if(id[w] == 0) DFS_Tarj(w);
if(onStack[w] == 1)
lowlink[x] = min(lowlink[w], lowlink[x]);
}
if(id[x] == lowlink[x])
{
nrctc++;
while(top > 0 and st[top] != x)
{
ctc[nrctc].push_back(st[top]);
onStack[st[top]] = 0;
lowlink[st[top]] = lowlink[x];
top--;
}
ctc[nrctc].push_back(x);
onStack[x] = 0;
top--;
}
}
int main()
{
int x, y, i;
in >> n >> m;
for(i = 1; i <= m; i++)
{
in >> x >> y;
a[x].push_back(y);
}
for(i = 1; i <= n; i++)
if(id[i] == 0) DFS_Tarj(i);
out << nrctc << "\n";
for(i = 1; i <= nrctc; i++)
{
for(auto w : ctc[i])
out << w << " ";
out << "\n";
}
return 0;
}