Pagini recente » Cod sursa (job #1854761) | Cod sursa (job #1045117) | Cod sursa (job #2138416) | Cod sursa (job #1664341) | Cod sursa (job #2928821)
#include <vector>
#include <fstream>
#include <stack>
#include<unordered_map>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, componente_conexe;
vector <vector <int>> sol;
vector <vector <int>> lista_adiacenta;
vector <vector <int>> lista_adiacenta_transpus;
unordered_map <int,int> vizitare;
stack <int> stiva;
void dfs(int nod)
{
for(int i=0; i < lista_adiacenta[nod].size();i++)
{
if(vizitare[lista_adiacenta[nod][i]]==0)
{
vizitare[lista_adiacenta[nod][i]]=1;
dfs(lista_adiacenta[nod][i]);
}
}
/// introducem nodurile vizitate in dfs intr-o stiva pentru a putea aplica apoi dfs-ul transpus
stiva.push(nod);
}
void dfs_transpus(int nod)
{
///daca nodul e vizitat in ambele dfs-uri, marcam diferit vizitarea
vizitare[nod] = -1;
///adaugam nodul in solutie
sol[componente_conexe].push_back(nod);
///in caz de nodurile vecine au fost vizitate apelam dfs_transpus
for( auto i = 0 ;i < lista_adiacenta_transpus[nod].size(); i++)
{
if(vizitare[lista_adiacenta_transpus[nod][i]] == 1)
{
dfs_transpus(lista_adiacenta_transpus[nod][i]);
}
}
}
int main()
{
int n, m;
cin>>n>>m;
lista_adiacenta.resize(n+1);
lista_adiacenta_transpus.resize(n+1);
for(int i=1; i <= m ; i++)
{ int a,b;
cin>>a>>b;
lista_adiacenta[a].push_back(b);
lista_adiacenta_transpus[b].push_back(a);
}
sol.resize(n+1);
vizitare.resize(n+1,0);
for(int i = 1; i <= n ; i++)
{
if(vizitare[i] == 0)
{
vizitare[i]=1;
dfs(i);
}
}
///cat timp avem elemente in stiva, verificam daca nodul a fost vizitat in dfs, iar apoi apelam dfs-ul transpus
while(stiva.size() > 0)
{
int nod = stiva.top();
stiva.pop();
if(vizitare[nod]==1)
{
componente_conexe++;
dfs_transpus(nod);
}
}
cout<<componente_conexe<<"\n";
///afisarea
for(int i=1; i <= componente_conexe ; i++)
{
for(auto nod: sol[i])
{
cout<< nod <<" ";
}
cout<<"\n";
}
return 0;
}