Pagini recente » Cod sursa (job #418042) | Cod sursa (job #760935) | Cod sursa (job #1510226) | Cod sursa (job #1396034) | Cod sursa (job #2155012)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define maxn 100005
#define maxm 200005
using namespace std;
int N, M; int nr;
vector <int> G [maxn]; //graful repr prin lista de adiacenta
int nivel[maxn], low[maxn], tata[maxn]; //nivelu in defeu, unde duce muchia de intoarcere si tatal fiecarui nod in arborele dfului
vector < vector <int> > sol; //matrice
bool vizitat[maxn]; //ii trebe la defeu
stack<int> stiva;
void biconex(int x)
{
vizitat[x] = 1;
nivel[x] = nivel[tata[x]] + 1;
low[x] = nivel[x]; //presupunem init ca toate nodurile sunt pct de articulatie si nu au muchii de intoarcere
stiva.push(x);
for(int i = 0; i < G[x].size(); ++i)
{
int succ = G[x][i];
if(vizitat[succ]) //am gasit o muchie de intoarcere
{
if(succ != tata[x])
low[x] = min(low[x], nivel[succ]);
continue;
}
tata[succ] = x;
biconex(succ);
low[x] = min(low[succ], low[x]);
if(nivel[x] <= low[succ]) //am gasit un punct de articulatie
{
sol.push_back(vector<int>(0));
int k;
do{
k = stiva.top();
stiva.pop();
sol[nr].push_back(k); //adaug elementele din stiva (subarborele df) intr-o singura componenta
}while(k!=succ);
sol[nr].push_back(x); //trec la urmatoarea componenta biconexa
++nr;
}
}
}
int main()
{
ifstream in ("biconex.in");
ofstream out ("biconex.out");
in>>N>>M;
for(int i = 0; i < M; ++i)
{
int x, y;
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if (!vizitat[i])
{
tata[i]=0;
biconex(i);
}
out<<nr<<"\n";
for(int i = 0; i < sol.size(); ++i)
{
for(auto it = sol[i].begin(); it != sol[i].end(); ++it)
out<<*it<<" ";
out<<'\n';
}
return 0;
}