Pagini recente » Cod sursa (job #3290484) | Cod sursa (job #3294047) | Diferente pentru implica-te/arhiva-educationala intre reviziile 206 si 223 | Cod sursa (job #3292331) | Cod sursa (job #3286793)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, nrc, nr;
vector<int>l[100005], sol[100005];
stack<int>s;
int num[100005], in_comp[100005], lowlink[100005];
void tarjan(int nod)
{
s.push(nod);
in_comp[nod]=1;
nr++;
lowlink[nod]=nr;
num[nod]=nr;
for(int i=0; i<l[nod].size(); i++)
{
int vecin=l[nod][i];
if(num[vecin]==0)
{
tarjan(vecin);
lowlink[nod]=min(lowlink[nod], lowlink[vecin]);
}
else if(in_comp[vecin])
{
lowlink[nod]=min(lowlink[nod], lowlink[vecin]);
}
}
if(lowlink[nod]==num[nod])
{
nrc++;
int x;
do{
x=s.top();
s.pop();
sol[nrc].push_back(x);
in_comp[x]=0;
}while(x!=nod);
}
}
int main()
{
fin>>n>>m;
while(m--)
{
int x, y;
fin>>x>>y;
l[x].push_back(y);
}
for(int i=1; i<=n; i++)
if(num[i]==0)
tarjan(i);
fout<<nrc<<"\n";
for(int i=1; i<=nrc; i++)
{
for(int j=0; j<sol[i].size(); j++)
fout<<sol[i][j]<<" ";
fout<<"\n";
}
return 0;
}