Pagini recente » Cod sursa (job #2942967) | Cod sursa (job #2940288) | Cod sursa (job #1883027) | Cod sursa (job #2965403) | Cod sursa (job #2925691)
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
map<int, list<int>> l;
vector<vector<int>> c;
vector<int> vect;
stack<int> s;
///ind -> memoreaza indicele nodurilor in ordinea in care sunt descoperite
///pmin -> reprezinta cel mai mic nivel pe care se afla un nod din stiva
///viz -> reprezinta starea de vizitare a unui nod
struct{
int ind, pmin;
bool viz;
}v[1000];
int cnt;
///algoritmul lui Tarjan
void ctc(int x)
{
///se memoreaza nivelul pe care se afla un nod in parcurgerea DFS, pornind din nodul de start cu care am intrat in functie
///contorul corespunde nivelului pe care se afla nodul curent in parcurgerea DFS
v[x].ind = cnt;
v[x].pmin = cnt;
cnt++;
int u;
///punem pe stiva nodurile in ordinea in care sunt vizitate pentru a tine evidenta
s.push(x);
///marcam nodul ca vizitat
v[x].viz = true;
///iteram prin fiecare nod care se afla in lista de adiacenta a nodului curent
for(auto it: l[x])
///in cazul in care indicele nivelului pe care se afla este -1(nu l-am determinat) atunci parcurgem recursiv functia cu
///nodul curent ca parametru, iar nivelul minim pe care s-a aflat nodul pentru care iterez prin lista de adiacenta devine
///minimul dintre nivelele minime ale nodului actual si al sau
if(v[it].ind == -1)
{
ctc(it);
v[x].pmin = min(v[x].pmin, v[it].pmin);
}
///altfel, daca nodul a fost vizitat atunci nivelul minim pe care s-a aflat nodul pentru care iterez prin lista de adiacenta
///devine minimul dintre nivelele minime ale nodului actual si al sau, dar fara a apela functia recursiv
else if(v[it].viz)
v[x].pmin = min(v[x].pmin, v[it].pmin);
///daca nivelul minim corespunde nivelului pe care am pus nodul atunci inseamna ca este radacina, deci iterez prin stiva care
///formeaza o componenta tare conexa, deci scot toate elementele din stiva si creez vectorul
if(v[x].pmin == v[x].ind)
{
vect.clear();
do
{
u = s.top();
s.pop();
v[u].viz = false;
vect.push_back(u);
}while(x != u);
///adaug componenta tare conexa in vectorul de componenete
c.push_back(vect);
}
}
int main()
{
int n, m, x, y, i;
in>>n>>m;
///creez lista de adiacenta
while(m)
{
in>>x>>y;
l[x].push_back(y);
m--;
}
///setez indicele pentru fiecare nod ca fiind -1, ceea ce inseamna ca nu l-am vizitat si nu stiu nivelul sau
for(i = 1; i <= n; i++)
v[i].ind = -1;
///caut noduri de inceput pentru componentele conexe, daca nivelul pe care se afla este inca -1
for(i = 1; i <= n; i++)
if(v[i].ind == -1)
ctc(i);
///afisez
for(auto it = 0; it < c.size(); it++)
{
for(auto it2: c[it])
out<<it2<<" ";
out<<endl;
}
return 0;
}