Cod sursa(job #1896036)

Utilizator vranceanu.andi2014Vranceanu Andi vranceanu.andi2014 Data 28 februarie 2017 13:26:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#define DMAX 100002
#include <vector>
using namespace std;

ifstream fin ("ctc.in");
ofstream fout("ctc.out");

vector <int> g[DMAX];
vector <int> gt[DMAX];
vector <int> ctc[DMAX];

bool uz[DMAX];
int n, m, poz, nr;
int posto[DMAX];
void citire();
void afisare();

void dfs(int x);
void dfst(int x);

int main()
{int i;
 citire();
 for(i=1; i<=n; i++)
     if(!uz[i]) dfs(i);
 for(i=n; i>0; i--)
     if(uz[posto[i]])
       {nr++;
        dfst(posto[i]);
       }
 afisare();
 return 0;
}
void citire()
{int i, x, y;
 fin>>n>>m;
 for(i=0; i<m; i++)
    {fin>>x>>y;
     //y intra in lista de adiacenta a lui x
     g[x].push_back(y);
     //x intra in lista de adiacenta a lui y
     gt[y].push_back(x);
    }
}
void dfs(int x)
{int i;
 uz[x]=1;
 //parcurg lista de adiacenta a lui x
 for(i=0; i<g[x].size(); i++)
    {if(!uz[g[x][i]])
        dfs(g[x][i]);
    }
 posto[++poz]=x;
}
void dfst(int x)
{int i;
 uz[x]=0;
 ctc[nr].push_back(x);
 //parcurg lista de adiacenta a lui x
 for(i=0; i<gt[x].size(); i++)
    {if(uz[gt[x][i]])
        dfst(gt[x][i]);
    }
}
void afisare()
{int i, j;
 fout<<nr<<'\n';
 for(i=1; i<=nr; i++)
    {for(j=0; j<ctc[i].size(); j++)
        fout<<ctc[i][j]<<' ';
     fout<<'\n';
    }
}