Pagini recente » Cod sursa (job #1243412) | Cod sursa (job #2955688) | Cod sursa (job #1045642) | Cod sursa (job #3200071) | Cod sursa (job #990972)
Cod sursa(job #990972)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int MAXN = 100005;
const int INF = 0x3f3f3f;
int a, b, n, m;
stack<pair<int, int> > stiva;
vector<vector<int> > matr;
struct graph {
vector<int> vecini;
int nivel;
int low;
}nods[MAXN];
void read() {
fin >> n >> m;
for (int i = 0; i < m; ++i) {
fin >> a >> b;
nods[a].vecini.push_back(b);
nods[b].vecini.push_back(a);
}
}
void extra_biconnex(int a, int b) {
vector<int> aux;
int x, y;
do {
x = stiva.top().first;
y = stiva.top().second;
stiva.pop();
aux.push_back(x);
aux.push_back(y);
}while (x != a || y != b);
matr.push_back(aux);//salvez componenta biconexa intr-o matrice
}
void dfs(int node, int father, int level) {
vector<int>::iterator it;
nods[node].nivel = nods[node].low = level;//marchez la ce nivel sunt, deci si ca am vizitat nodul 'node'
for (it = nods[node].vecini.begin(); it != nods[node].vecini.end(); ++it) {
if (*it == father) continue;//daca avem de a face cu tatal nodului, sarim
if (nods[*it].nivel == -1) {//daca vecinul *it nu a fost vizitat
stiva.push(make_pair(node, *it));//bag muchia in stiva
dfs(*it, node, level + 1);//continui DFS-ul cu vecinul *it al lui 'node'
nods[node].low = min(nods[node].low, nods[*it].low);//daca *it a gasit un nivel minim mai mic, salvam
if (nods[node].nivel <= nods[*it].low)
extra_biconnex(node, *it);
}else
nods[node].low = min(nods[node].low, nods[*it].nivel);
}
}
void write() {
fout << matr.size() << '\n';//nr componente biconexe
for (unsigned i = 0; i < matr.size(); ++i) {
sort(matr[i].begin(), matr[i].end());//sortam
matr[i].push_back(matr[i][matr[i].size() - 1]);
for (unsigned j = 0; j < matr[i].size(); j += 2) {
fout << matr[i][j] << ' ';
}
fout << '\n';
}
}
int main(){
read();
for (int i = 0; i <= n; ++i)
nods[i].nivel = -1;//in nodurile cu -1 nu am fost inca; la inceput nu am fost in niciun nod
dfs(1, 0, 1);
write();
fin.close();
fout.close();
return 0;
}