Pagini recente » Cod sursa (job #3215752) | Cod sursa (job #3270415) | Cod sursa (job #846373) | Cod sursa (job #2639231) | Cod sursa (job #781811)
Cod sursa(job #781811)
#include <fstream>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,x,y,nrctc;
vector<int> G[MAXN],GT[MAXN],ctc[MAXN],post;
bool uz[MAXN];
void DFS(int p);
void DFS_T(int p);
int main()
{
int i,j;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);}
for(i=1;i<=n;i++)
if(!uz[i])
DFS(i);
for(i=1;i<=n;i++)
uz[i]=0;
for(i=post.size()-1;i>=0;i--){
if(!uz[post[i]]){
nrctc++;
DFS_T(post[i]);}}
g<<nrctc<<'\n';
for(i=1;i<=nrctc;i++){
for(j=0;j<ctc[i].size();j++)
g<<ctc[i][j]<<' ';
g<<'\n';}
f.close();
g.close();
return 0;
}
void DFS(int p){
int i;
uz[p]=1;
for(i=0;i<G[p].size();i++)
if(!uz[G[p][i]])
DFS(G[p][i]);
post.push_back(p);}
void DFS_T(int p){
int i;
uz[p]=1;
ctc[nrctc].push_back(p);
for(i=0;i<GT[p].size();i++)
if(!uz[GT[p][i]])
DFS_T(GT[p][i]);}