Pagini recente » Cod sursa (job #559541) | Cod sursa (job #2047133) | Cod sursa (job #1342576) | Cod sursa (job #3243583) | Cod sursa (job #2928405)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <vector <int>> lista_adiacenta;
vector <vector <int>> lista_adiacenta_transpusa;
vector <vector <int>> solutie;
vector <int> stiva;
vector <int> nivel;
void dfs(int a)
{
int j;
for(long unsigned j=0; j<lista_adiacenta[a].size(); j++)
{
if(nivel[lista_adiacenta[a][j]]==0)
{
nivel[lista_adiacenta[a][j]]=1;
dfs(lista_adiacenta[a][j]);
}
}
stiva.push_back(a);
}
void dfs_transpus(int a)
{
int j;
solutie[nrcomponente].push_back(a);
nivel[a]=2;
for(long unsigned j=0; j<lista_adiacenta_transpusa[a].size(); j++)
{
if(nivel[lista_adiacenta_transpusa[a][j]]==1)
{
dfs_t(lista_adiacenta_transpusa[a][j]);
}
}
}
int main()
{
int a, b, noduri, muchii ,nod, i;
f>>noduri>>muchii;
lista_adiacenta.resize(noduri+1);
lista_adiacenta_transpusa.resize(noduri+1);
nivel.resize(noduri+1);
solutie.resize(noduri+1);
for(i=0; i<muchii; i++)
{
f>>a>>b;
lista_adiacenta[a].push_back(b);
lista_adiacenta_transpusa[b].push_back(a);
}
for(i=1; i<=noduri; i++)
{ nivel[i]=0;
}
for(i=1; i<=noduri; i++)
{
if(nivel[i]==0)
{
nivel[i]=1;
dfs(i);
}
}
while(!stiva.empty())
{
nod=stiva.back();
stiva.pop_back();
if(nivel[nod]==1)
{
nrcomponente++;
dfs_transpust(nod);
}
}
g<<nrcomponente<<endl;
for(i=1; i<=nrcomponente; i++)
{
for(long unsigned int j=0; j<solutie[i].size(); j++)
{
g<<solutie[i][j]<<" ";
}
g<<endl;
}
return 0;
}