Pagini recente » Cod sursa (job #1148084) | Cod sursa (job #2206836)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,j,a,b,id,rz,nr,f[NMAX],low[NMAX];
bool estq[NMAX];
vector<int> vec[NMAX];
deque<int> q;
vector<int> cmp[NMAX];
void tarjan(int x)
{
q.push_back(x);
estq[x]=1;
low[x]=id;
f[x]=id++;
for(int i=0;i<vec[x].size();i++)
{
if(!f[vec[x][i]])
{
tarjan(vec[x][i]);
low[x]=min(low[x],low[vec[x][i]]);
}
else if(estq[vec[x][i]]) low[x]=min(low[x],f[vec[x][i]]);
}
if(low[x]==f[x])
{
rz++;
do
{
nr=q.back();
estq[nr]=0;
cmp[rz].push_back(nr);
q.pop_back();
}while(nr!=x);
}
}
int main() {
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
vec[a].push_back(b);
}
id=1;
for(i=1;i<=n;i++)
if(f[i]==0)
{
tarjan(i);
}
fout<<rz<<"\n";
for(i=1;i<=rz;i++)
{
for(j=0;j<cmp[i].size();j++)
fout<<cmp[i][j]<<" ";
fout<<"\n";
}
}