Pagini recente » Cod sursa (job #1608762) | Cod sursa (job #998885) | Cod sursa (job #2746332) | Cod sursa (job #2353592) | Cod sursa (job #2666928)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int vizitat[100001], nrCompTareConexe; //un vector de muchii vizitate
vector<int> listaMuchii[100001], listaMuchiiTranspusa[100001]; //vector pentru lista de muchii si lista de muchii transpuse
vector<int> componenteTareConexe[100005]; //vector pentru componentele tare conexe
stack<int> stiva; // folosim o stiva pentru a retine parcurgerea grafului si pt a adauga recursiv elementele in aceasta
void dfs(int nod)
{
int vecin;
vizitat[nod] = 1; //marcam cu 1 prima parcurgere in adancime a fiecarui nod
for (int i = 0; i < listaMuchii[nod].size(); i++)
{
vecin = listaMuchii[nod][i];
if (!vizitat[vecin])
dfs(vecin);
}
stiva.push(nod);
}
void dfs_transpus(int nod)
{
int vecin;
vizitat[nod] = 2; //marcam cu 2 a doua parcurgere a unui nod din graful transpus
componenteTareConexe[nrCompTareConexe].push_back(nod); //adaugam in lista de componente tare conexe nodul in lista in care apartine
for (int i = 0; i < listaMuchiiTranspusa[nod].size(); i++)
{
vecin = listaMuchiiTranspusa[nod][i];
//verificam daca vecinul a fost vizitat in prima parcurgere de dfs
if (vizitat[vecin] == 1)
dfs_transpus(vecin);
}
}
int main()
{
int x, y, i, noduri, muchii, nodCurent;
fin >> noduri >> muchii;
//facem lista de muchii/adiacenta ale grafului
for (i = 1; i <= muchii; i++)
{
fin >> x >> y;
listaMuchii[x].push_back(y); //inseram in lista de muchii
listaMuchiiTranspusa[y].push_back(x); //inseram muchia cu directie opus in lista de muchii transpuse
}
//parcurgem graful in adancime pentru a stabili ordinea nodurilor si pentru a umple stiva
for (i = 1; i <= noduri; i++)
{
if (vizitat[i] == 0)
dfs(i);
}
while (!stiva.empty())
{
//nodul curent va fi ultimul element introdus din stiva
nodCurent = stiva.top();
//daca a fost vizitat in prima parcurgere cu dfs vom mari numarul de componente tari conexe si
//le vom cauta si pe restul din aceeasi componenta tare conexa
if (vizitat[nodCurent] == 1)
{
nrCompTareConexe++;
dfs_transpus(nodCurent);
}
stiva.pop();
}
fout << nrCompTareConexe << '\n';
for (i = 1; i <= nrCompTareConexe; i++)
{
for (int j = 0; j < componenteTareConexe[i].size(); j++)
{
fout << componenteTareConexe[i][j] << " ";
}
fout << '\n';
}
return 0;
}