Pagini recente » Cod sursa (job #1252244) | Cod sursa (job #937444) | Cod sursa (job #1937068) | Cod sursa (job #2649792) | Cod sursa (job #1339932)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector <int> v[nmax];
void read() {
int x, y;
fin >> n >> m;
for (int i = 1; i <= m; i++)
fin >> x >> y,
v[x].push_back(y),
v[y].push_back(x);
}
int nrComp;
stack < pair<int, int> > s;
vector <int> comp[nmax];
int nivel[nmax], tata[nmax], low[nmax];
bool viz[nmax];
void newComp(int nod, int vc) {
nrComp++;
int x = s.top().first;
int y = s.top().second;
s.pop();
while (x != nod && y != vc) {
comp[nrComp].push_back(x);
comp[nrComp].push_back(y);
x = s.top().first;
y = s.top().second;
s.pop();
}
comp[nrComp].push_back(x);
comp[nrComp].push_back(y);
}
void dfs(int nodCurent) {
viz[nodCurent] = true;
for (int i = 0; i < v[nodCurent].size(); i++) {
int vecinCurent = v[nodCurent][i];
if (!viz[vecinCurent]) {
nivel[vecinCurent] = low[vecinCurent] = nivel[nodCurent] + 1;
tata[vecinCurent] = nodCurent;
s.push(make_pair(nodCurent, vecinCurent));
dfs(vecinCurent);
low[nodCurent] = min(low[nodCurent], low[vecinCurent]);
if (low[vecinCurent] >= nivel[nodCurent]) {
// componenta noua
newComp(nodCurent, vecinCurent);
}
} else if (tata[nodCurent] != vecinCurent)
low[nodCurent] = min(low[nodCurent], nivel[vecinCurent]);
}
}
void solve() {
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
fout << nrComp << "\n";
for (int i = 1; i <= nrComp; i++) {
sort(comp[i].begin(), comp[i].end());
for (int j = 1; j < comp[i].size(); j++)
if (comp[i][j-1] != comp[i][j])
fout << comp[i][j-1] << " ";
fout << comp[i][comp[i].size()-1] << "\n";
}
}
int main() {
read();
solve();
fin.close();
fout.close();
return 0;
}