Pagini recente » Cod sursa (job #1104731) | Cod sursa (job #259938) | Cod sursa (job #1708511) | Cod sursa (job #1344957) | Cod sursa (job #1042280)
#include<cstdio>
#include<vector>
#define NMAX 100000
using namespace std;
FILE* fin=fopen("ctc.in", "r");
FILE* fout=fopen("ctc.out", "w");
int n,m,nr,nrctc;
int viz[NMAX],postordine[NMAX];
vector<int> G[NMAX];
vector<int> GT[NMAX];
vector<int> ma[NMAX];
/*
//varianta 1
int D[NMAX][NMAX],n,viz[NMAX],m,x,y;
void citire()
{
int i,j;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
D[x][y]=1;
}
}
void construire()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(D[i][k] && D[k][j])
D[i][j]=1;
}
void rezolvare(int x)
{
int i,j;
for(j=1;j<=n;j++)
{
if(viz[j]==0)
{
viz[j]=1;
fout<<j<<" ";
for(i=1;i<=n;i++)
{
if(D[j][i]==1 && D[i][j]==1 && viz[i]==0)
{
viz[i]=1;
fout<<i<<" ";
}
}
fout<<"\n";
}
}
}
int main()
{
citire();
construire();
rezolvare(1);
}*/
void citire() //citire
{
int i,x,y;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&x,&y);
G[x].push_back(y); //graf
GT[y].push_back(x); //graful transpus
}
}
void DFS(int vf)
{
int i;
viz[vf]=1;
for(i=0;i<G[vf].size();i++)
if(viz[G[vf][i]]==0) //daca vf nu a fost vizitat mai fac un DFS.
DFS(G[vf][i]);
postordine[++nr]=vf; //pun vf in vectorul postordine cand nu mai am noduri accesibile
}
void DFST(int vf)
{
int i;
viz[vf]=0;
ma[nrctc].push_back(vf);
for(i=0;i<GT[vf].size();i++)
if(viz[GT[vf][i]]==1)
DFST(GT[vf][i]);
}
void afisare()
{
int i,j;
fprintf(fout,"%d",nrctc);
fprintf(fout,"%s","\n");
for(i=0;i<nrctc;i++)
{
for(j=0;j<ma[i].size();j++)
fprintf(fout,"%d ",ma[i][j]);
fprintf(fout,"%s","\n");
}
}
int main()
{
int i;
citire();
for(i=1;i<=n;i++)
if(viz[i]==0) //daca vf nu a fost vizitat fac DFS
DFS(i);
for(i=n;i>=1;i--) //parcurg vectorul postordine de la dreapta la stanga
if(viz[postordine[i]]==1) //daca vf
{
DFST(postordine[i]);
nrctc++; //cresc nr de componente
}
afisare();
return 0;
}