Pagini recente » Borderou de evaluare (job #3356212) | Borderou de evaluare (job #3306822) | Cod sursa (job #3336088)
#include <bits/stdc++.h>
#define NMAX 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,nrctc;
bool viz[NMAX];
vector<int>a[NMAX];
vector<int>ta[NMAX];
stack<int>s;
vector<int>ctc[NMAX];
void citire();
void dfs1(int x);
void dfs2(int x);
int main()
{
int i,j;
citire();
for(i=1;i<=n;i++)
if(!viz[i])
dfs1(i);
for(i=1;i<=n;i++) viz[i]=0;
while(!s.empty())
{
i=s.top(); s.pop();
if(!viz[i])
{
dfs2(i);
nrctc++;
}
}
fout<<nrctc<<'\n';
for(i=0;i<nrctc;i++)
{
for(j=0;j<ctc[i].size();j++)
fout<<ctc[i][j]<<' ';
fout<<'\n';
}
return 0;
}
void citire()
{
int i,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
a[x].push_back(y);
ta[y].push_back(x);
}
}
void dfs1(int x)
{
int i;
viz[x]=1;
for(i=0;i<a[x].size();i++)
if(!viz[a[x][i]])
dfs1(a[x][i]);
s.push(x);
}
void dfs2(int x)
{
int i;
viz[x]=1;
ctc[nrctc].push_back(x);
for(i=0;i<ta[x].size();i++)
if(!viz[ta[x][i]])
dfs2(ta[x][i]);
}