Pagini recente » Cod sursa (job #1548463) | Cod sursa (job #1120594) | Cod sursa (job #855214) | Cod sursa (job #2394450) | Cod sursa (job #2929517)
/**
DESCRIEREA REZOLVARII: complexitate O(N + M)
Am utilizat ALGORITMUL LUI TARJAN care presupune:
1.Pt fiecare nod nevizitat pornim o parcurgere dfs
2.La vizitarea unui nod acesta este adaugat pe stiva si primeste un id
3.Pentru nodul curent vizitam totate nodurile adiacente
4.Deoarece oferim id-urile in ordine crescatoare, primul nod vizitat dintr-o componenta conexa ca vi nodul cu id-ul cel mai mic
astfel, cand ajungem cu parcurgerea la un nod cu un id mai mic, stim ca apartin aceleiasi componente conexe
5.dupa acest procedeu, daca id-ul curent este egal cu low-ul, nodul curent este un nod de "inceput" pentru componenta conexa a lui
asftel scoatem de pe stack nodurile pana ajungem la cel curent, iar acestea vor fi parte a componentei conexe curente
**/
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack <int> stiva;
vector <int> adiacenta[100001];
vector <vector <int>> rez;
int id[100001],verif[100001], low[100001], idcurent=1,componente=0;
//verif ne spune daca un nod se afla sau nu pe stiva
//id ne spune daca un nod a fost sau nu vizitat, iar daca da, ce Id a primit
void dfs(int curent) {
id[curent] = idcurent;
low[curent] = idcurent;
idcurent++;
stiva.push(curent);
verif[curent] = 1;
for (int i=0;i < adiacenta[curent].size();i++) {
if (id[ adiacenta[curent][i]] == 0) {
dfs(adiacenta[curent][i]);
low[curent] = min(low[curent], low[adiacenta[curent][i]]);
}
else if (verif[adiacenta[curent][i]]) {
low[curent] = min(low[curent], id[adiacenta[curent][i]]);
}
}
if (id[curent] == low[curent]) {
vector <int> comp;
int node;
node = stiva.top();
stiva.pop();
verif[node] = 0;
comp.push_back(node);
while (curent != node) {
node = stiva.top();
stiva.pop();
verif[node] = 0;
comp.push_back(node);
} ;
rez.push_back(comp);
componente++;
}
}
int main() {
int n,m,x,y;
f>>n>>m;
for (int i = 1; i <= m; i++)
{
f>>x>>y;
adiacenta[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (id[i] == 0) {
dfs(i);
}
}
g<< componente <<'\n';
for (int i = 0; i < rez.size(); i++) {
for (int j = 0; j < rez[i].size(); j++) {
g<< rez[i][j] << " ";
}
g<<'\n';
}
return 0;
}