Pagini recente » Cod sursa (job #2605277) | Cod sursa (job #3200801) | Cod sursa (job #3185647) | Cod sursa (job #495062) | Cod sursa (job #2784301)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int vizitat[100005];
int moment[100005]; //vector ce retine momentul in care se viziteaza prima oara un nod di graf
int low[100005]; //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
stack<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment
vector<set<int>> tareconexe; //vectorul de componente tare-conexe
int n, m, timp=0; // timp = contor de timp pentru crearea vectorului moment
vector<vector<int>> la;
void dfs(int x) //x = nodul curent
{
vizitat[x] = 1;
moment[x] = timp++;
low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
in_stack.insert(x);
//parcurg lista de adiacente a lui x
for(int i=0; i<la[x].size(); ++i)
{
int z = la[x][i];
if (vizitat[z] == 0)
{
dfs(z);
//daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
if(low[x] > low[z])
low[x] = low[z];
}
else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
{
//daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
// strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
// (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
if (low[x] > moment[z])
low[x] = moment[z];
}
}
if(low[x]==moment[x]) //daca nodul e radacina in componenta curenta(am avut un circuit)
{
set<int> componenta;
int y;
do{
y=stiva.top();
stiva.pop();
in_stack.erase(y);
componenta.insert(y);
}while(y!=x);
tareconexe.push_back(componenta);
}
}
int main()
{
fin>>n>>m;
la.resize(n+1);
for(int i=0; i<m; ++i)
{
int x ,y;
fin >> x >> y;
la[x].push_back(y);
}
//daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
for(int j=1; j<=n; ++j)
if(vizitat[j]==0)
dfs(j);
fout << tareconexe.size() << "\n";
for(int i=0; i<tareconexe.size(); ++i)
{
for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
fout << *it << " ";
fout << "\n";
}
}