Pagini recente » Cod sursa (job #40180) | Cod sursa (job #2928621)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
//declaram o variabila globala care sa contorizeze numarul variabilelor globale
int n, nr_comp_conex;
//construim un vector de vectori in care retinem nodurile pe care le contine fiecare componenta conexa
vector <vector <int>> solutie;
//vom folosi 2 liste de adiacenta, intrucat avem un graf orientat
vector <vector <int>> ad_1; //lista adiacenta
vector <vector <int>> ad_2; //lista adiacenta inversa
vector <int> vizitat;
stack <int> st;
ifstream f("ctc.in");
ofstream g("ctc.out");
void afisare()
{
g<<nr_comp_conex<<"\n";
//afisam nodurile pe care le contine fiecare componenta conexa
for( long long int i=1; i <= nr_comp_conex ; i++)
{
for(auto v: solutie[i])
{
g<< v <<" ";
}
g<<"\n";
}
}
void dfs_1(int nod)
{
for(auto i=0; i < ad_1[nod].size();i++)
{
if(vizitat[ad_1[nod][i]]==0)
{
vizitat[ad_1[nod][i]]=1;
dfs_1(ad_1[nod][i]);
}
}
// introducem nodurile vizitate in dfs 1 intr-o stiva pentru a putea aplica apoi dfs 2
st.push(nod);
}
void dfs_2(int nod)
{
//intrucat nodul a fost vizitat in ambele dfs, vom atribui valoarea 2 in vectorul vizitat
vizitat[nod] = 2;
//vom adauga nodul in componenta conexa
solutie[nr_comp_conex].push_back(nod);
//parcurgem vecinii nodului curent. Daca acestia au fost vizitate in dfs_1, atunci apelam dfs_2
for( auto i = 0 ;i < ad_2[nod].size(); i++)
{
if(vizitat[ad_2[nod][i]] == 1)
{
dfs_2(ad_2[nod][i]);
}
}
}
creare_lista(int m)
{
for(int i=1;i <= m ; i++)
{ int a,b;
f>>a>>b;
ad_1[a].push_back(b);
ad_2[b].push_back(a);
}
}
int main()
{
int m,nod,i;
f>>n>>m;
solutie.resize(n+1);
vizitat.resize(n+1,0);
ad_1.resize(n+1);
ad_2.resize(n+1);
//folosim un for pentru a citi muchiile din graf si construim 2 liste de adiacenta: cea propriu-zisa si cea inversa
creare_lista(m);
//parcurgem vectorul in care contorizam daca modurile au fost vizitate sau nu atat in dfs_1 cat si in dfs_2
for(int i = 1; i <= n ; i++)
{ //daca nodul nu a fost vizitat, atunci il marcam ca vizitat in dfs_1 si apoi apelam functia dfs_1
if(vizitat[i] == 0)
{
vizitat[i]=1;
dfs_1(i);
}
}
//cat timp stiva contine elemente, atunci verificam daca acesta a fost vizitat in dfs_1 si apoi facem dfs_2(parc urgerea in ordine inversa)
while(st.size() > 0)
{
nod = st.top();
st.pop();
if(vizitat[nod]==1)
{
nr_comp_conex++;
dfs_2(nod);
}
}
afisare();
return 0;
}