Pagini recente » Cod sursa (job #1129572) | Cod sursa (job #1145272) | Cod sursa (job #1317924) | Cod sursa (job #3170632) | Cod sursa (job #2719237)
/**Dându-se un graf orientat G = (V, E) se cere să se determine componentele sale tare conexe.**/
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define maxn 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> graf[maxn];
vector<int> trgraf[maxn];
vector<int> ctc[maxn];
stack <int> ordineNoduri;
int vizite[maxn];
void DFS_graf(int nod,int n)
{
unsigned int i;
int vecin;
vizite[nod]=1;
//zona 1
for(i=0;i<graf[nod].size();i++)
{ //zona 2
vecin=graf[nod][i];
if(vizite[vecin]==0)
{
DFS_graf(vecin,n);
} //zona 3
} //zona 4
ordineNoduri.push(nod);
}
void DFS_trgraf(int nod,int n,int nrctc)
{
unsigned int i;
int vecin;
vizite[nod]=2;
ctc[nrctc].push_back(nod);
//zona 1
for(i=0;i<trgraf[nod].size();i++)
{ //zona 2
vecin=trgraf[nod][i];
if(vizite[vecin]==1)
{
DFS_trgraf(vecin,n,nrctc);
} //zona 3
} //zona 4
}
int kosaraju(int n)
{
int nod;
int nrctc=0;
for(nod=1;nod<=n;nod++)
{
if(vizite[nod]==0)
{
DFS_graf(nod,n);
}
}
while(!ordineNoduri.empty())
{
nod=ordineNoduri.top();
cout<<nod;
if(vizite[nod]==1)
{
nrctc++;
DFS_trgraf(nod,n,nrctc);
}
ordineNoduri.pop();
}
return nrctc;
}
int main()
{
int n,m,x,y,i;
int nrctc;
unsigned int j;
fin>>n>>m;
for(i=0;i<m;i++)
{
fin>>x>>y;
graf[x].push_back(y);
trgraf[y].push_back(x);
}
nrctc=kosaraju(n);
fout<<nrctc<<'\n';
for(i=1;i<=nrctc;i++)
{
for(j=0;j<ctc[i].size();j++)
{
fout<<ctc[i][j]<<' ';
}
fout<<'\n';
}
return 0;
}