Pagini recente » Cod sursa (job #2335646) | Cod sursa (job #3314212) | Cod sursa (job #3314315) | Cod sursa (job #846184) | Cod sursa (job #1147852)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define DIMN 100100
#define DIMM 200100
using namespace std;
vector<int> L[DIMN];
stack < pair<int, int> > s;
pair<int,int> p;
vector< int > C[DIMM];
int Niv[DIMN],Low[DIMN],i,j,n,m,x,y,cb;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void dfs(int nod, int parent, int niv) {
Niv[nod] = niv;
Low[nod] = niv;
for (int i=0; i<L[nod].size(); i++) {
if (L[nod][i] == parent)
continue;
if (Niv[ L[nod][i] ] == 0) {
// cand inaintez pun in stiva muchiile de avansare
s.push( make_pair(nod, L[nod][i] ) );
// fiecare pornire cu autoapel intr-un fiu poate provoca o componenta biconexa generata de muchia pe care pornesc
dfs(L[nod][i], nod, niv+1);
// daca la intoarcerea din autoapelul pe aceasta muchie nu am coborat sub nivelul nodului curent inseamna ca muchia pe care tocmai am terminat genereaza o cb
if (Niv[nod] <= Low[ L[nod][i] ] ) {
// scot din stiva pana intalnesc aceasta muchie nod, L[nod][i]
// componanta biconexa are ca si noduri extremitatile muchiilor puse in stiva dupa muchia ce a generat-o deci scot din stiva pana intalnesc acea muchuie
cb++;
do {
p = s.top();
s.pop();
C[cb].push_back(p.first);
C[cb].push_back(p.second);
} while (p.first != nod || p.second!=L[nod][i]);
}
}
Low[nod] = min (Low[nod], Low[ L[nod][i] ]);
}
}
int main() {
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
for (i=1;i<=n;i++)
if (Niv[i] == 0) {
dfs(i, 0, 1);
}
fout<<cb<<"\n";
for (i=1;i<=cb; i++) {
sort(C[i].begin(), C[i].end());
fout<<C[i][0]<<" ";
for (j=1; j<C[i].size(); j++)
if (C[i][j] != C[i][j-1])
fout<<C[i][j]<<" ";
fout<<"\n";
}
return 0;
}