Pagini recente » Cod sursa (job #86064) | Cod sursa (job #1723005) | Cod sursa (job #2411984) | Cod sursa (job #636845) | Cod sursa (job #1977076)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100002
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> graf[NMAX], biconexe[NMAX];
int nrBic = 0;
int ind[NMAX], lowlink[NMAX], idx = 0;
stack< pair<int, int> > stiva;
void getBicon(int nodex, int nodey) {
int x, y;
do {
x = stiva.top().first;
y = stiva.top().second;
stiva.pop();
biconexe[nrBic].push_back(x);
biconexe[nrBic].push_back(y);
}while(make_pair(nodex, nodey) != make_pair(x, y));
nrBic++;
}
void DFS(int node) {
ind[node] = lowlink[node] = ++idx;
for (auto& adj: graf[node]) {
if (!ind[adj]) {
stiva.push(make_pair(node, adj));
DFS(adj);
lowlink[node] = min(lowlink[node], lowlink[adj]);
if (ind[node] <= lowlink[adj])
getBicon(node, adj);
}
else
lowlink[node] = min(lowlink[node], ind[adj]);
}
}
int main() {
int N, M;
fin >> N >> M;
int x, y;
while (M--) {
fin >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
if (!ind[i])
DFS(i);
fout << nrBic << "\n";
for (int i = 0; i < nrBic; ++i) {
sort(biconexe[i].begin(), biconexe[i].end());
biconexe[i].erase(unique(biconexe[i].begin(), biconexe[i].end()), biconexe[i].end());
for (auto& node: biconexe[i])
fout << node << " ";
fout << "\n";
}
return 0;
}