Pagini recente » Cod sursa (job #633544) | Cod sursa (job #1032280) | Cod sursa (job #1781438) | Cod sursa (job #877614) | Cod sursa (job #2797524)
#include<bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector<int> lista_adiacenta[100001], lista_adiacenta2[100001], componente[100001], stiva;
unordered_map<int,bool> vector_vizitat,vector_vizitat_2;
int n,m,x,y,nr_componente_tari_conexe;
void DFS1(int x)
{
vector_vizitat[x] = true;
for (int i=0; i <lista_adiacenta[x].size(); ++i)
if (vector_vizitat[lista_adiacenta[x][i]]==0)
DFS1(lista_adiacenta[x][i]);
stiva.push_back(x);
}
void DFS2(int x)
{
vector_vizitat_2[x] = true;
componente[nr_componente_tari_conexe].push_back(x);
for (int i = 0; i < lista_adiacenta2[x].size(); ++i)
if (vector_vizitat_2[lista_adiacenta2[x][i]]==0)
DFS2(lista_adiacenta2[x][i]);
}
int main()
{
fin>>n>>m;
for(int i=0; i<m; i++)
{
fin>>x>>y;
lista_adiacenta[x].push_back(y);
lista_adiacenta2[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!vector_vizitat[i])
DFS1(i);
for(int i=stiva.size()-1;i>=0 ;i--)
{
if(!vector_vizitat_2[stiva[i]])
{
DFS2(stiva[i]);
nr_componente_tari_conexe++;
}
}
fout<<nr_componente_tari_conexe<<'\n';
for(int i=0 ;i <nr_componente_tari_conexe ; i++)
{
for(int j = 0; j <componente[i].size(); j++)
fout<<componente[i][j]<<" ";
fout<<'\n';
}
return 0;
}