Cod sursa(job #523272)

Utilizator bacilaBacila Emilian bacila Data 17 ianuarie 2011 17:09:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include<iostream>
#include <vector>
using namespace std;
vector<int> p[100002],pt[100002],cmp[100002];
int po[100002],viz[100002],n,nrc,nr;
ofstream g("ctc.out");
void cit(){
ifstream f("ctc.in");
int x,y,m,i;
f>>n>>m;
for(i=1;i<=n;i++){
p[i].push_back(0); pt[i].push_back(0); cmp[i].push_back(0);}
for(i=1;i<=m;i++)
{f>>x>>y;
p[x][0]++;
p[x].push_back(y);
pt[y][0]++;
pt[y].push_back(x);
}
f.close();}

void dfs(int x)
{ int i;
viz[x]=1;
for(i=1;i<=p[x][0];i++)
if(!viz[p[x][i]])
dfs(p[x][i]);
po[++nr]=x;}

void dfst(int x)
{ int i; 
viz[x]=0; cmp[nrc][0]++; cmp[nrc].push_back(x);
for(i=1;i<=pt[x][0];i++)
if(viz[pt[x][i]])
dfst(pt[x][i]);
}

void afi()
{int i,j;
     
g<<nrc<<'\n';
for(i=1;i<=nrc;i++){
for(j=1;j<=cmp[i][0];j++)
g<<cmp[i][j]<<" ";
g<<'\n';}
  g.close();

}

int main ()
{int i;
cit();
for(i=1;i<=n;i++)
if(!viz[i]) dfs(i);
for(i=n;i;i--)
if(viz[po[i]]){nrc++; dfst(po[i]);
}
afi();
return 0;
}