Cod sursa(job #324784)

Utilizator mihaionlyMihai Jiplea mihaionly Data 17 iunie 2009 13:38:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <vector>
#include <fstream>
using namespace std;
#define nmax 100001
vector<int> a[nmax],at[nmax],sol[nmax];
int viz[nmax],n,m,p[nmax],nr,nrc;
ifstream f("ctc.in");
ofstream g("ctc.out");
void read()
 {
 f>>n>>m;
 int x,y,i;
 for(i=1;i<=n;i++)
  {
  a[i].push_back(0);
  at[i].push_back(0);
  }
 for(i=1;i<=m;i++)
  {
  f>>x>>y;
  a[x][0]++;
  a[x].push_back(y);
  at[y][0]++;
  at[y].push_back(x);
  }
 }
void dfs(int x)
 {
 viz[x]=1;
 p[++nr]=x;
 for(int i=1;i<=a[x][0];i++)
  if(!viz[a[x][i]])
   dfs(a[x][i]);
 }
void dfst(int x)
 {
 viz[x]=0;
 sol[nrc][0]++;
 sol[nrc].push_back(x);
 for(int i=1;i<=at[x][0];i++)
  if(viz[at[x][i]])
   dfst(at[x][i]);
 }
void show()
 {
 g<<nrc<<endl;
 int i,j;
 for(i=1;i<=nrc;i++)
  {
  for(j=1;j<=sol[i][0];j++)
   {
   g<<sol[i][j]<<" ";
   }
  g<<endl;
  }
 }
int main()
 {
 int i;
 read();
 for(i=1;i<=n;i++)
  if(!viz[i])
   dfs(i);    
 for(i=1;i<=n;i++)
  {
  if(viz[p[i]])
   {
   nrc++;
   sol[nrc].push_back(0);
   dfst(p[i]);
   }
  }
 show();
 return 0;
 }