Pagini recente » Cod sursa (job #2071111) | Cod sursa (job #2386322) | Cod sursa (job #1645727) | Cod sursa (job #1747836) | Cod sursa (job #1366726)
#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, nrComp;
int low[nmax], tata[nmax], nivel[nmax];
bool viz[nmax];
stack < pair<int, int> > s;
vector <int> G[nmax], comp[nmax];
void newComp(int nod, int vecin) {
nrComp++;
int x = s.top().first;
int y = s.top().second;
s.pop();
while (x != nod && y != vecin) {
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] = 1;
for (int i = 0; i < G[nodCurent].size(); i++) {
int vecinCurent = G[nodCurent][i];
if (!viz[vecinCurent]) {
nivel[vecinCurent] = nivel[nodCurent] + 1;
low[vecinCurent] = nivel[vecinCurent];
tata[vecinCurent] = nodCurent;
s.push(make_pair(nodCurent, vecinCurent));
dfs(vecinCurent);
low[nodCurent] = min(low[nodCurent], low[vecinCurent]);
if (low[vecinCurent] >= nivel[nodCurent])
newComp(nodCurent, vecinCurent);
} else if (tata[nodCurent] != vecinCurent) {
low[nodCurent] = min(low[nodCurent], nivel[vecinCurent]);
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
fout << nrComp << "\n";
for (int i = 1; i <= nrComp; i++) {
sort(comp[i].begin(), comp[i].end());
fout << comp[i][0] << " ";
for (int j = 1; j < comp[i].size(); j++)
if (comp[i][j] != comp[i][j-1])
fout << comp[i][j] << " ";
fout << "\n";
}
fin.close();
fout.close();
return 0;
}