Pagini recente » Cod sursa (job #1711382) | Cod sursa (job #1270413) | Cod sursa (job #2913909) | Cod sursa (job #2848329) | Cod sursa (job #2178863)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector< vector< int > > G, componenteBiconexe;
vector< int > discoveryTime, lowestTime;
stack< pair< int, int > > s;
void updateBiconnectedComponents(int u, int v) {
vector< int > newComponent;
int tempU, tempV;
do {
tempU = s.top().first; tempV = s.top().second; s.pop();
newComponent.push_back(tempU); newComponent.push_back(tempV);
} while(tempU != u || tempV != v);
componenteBiconexe.push_back(newComponent);
}
void DFS(int node, int fatherNode, int currentTime) {
discoveryTime[node] = lowestTime[node] = currentTime;
for(auto vecin: G[node]) {
if(vecin == fatherNode) {
continue;
}
if(discoveryTime[vecin] == -1) {
s.push(make_pair(node, vecin));
DFS(vecin, node, currentTime + 1);
lowestTime[node] = min(lowestTime[node], lowestTime[vecin]);
if(lowestTime[vecin] >= discoveryTime[node]) {
updateBiconnectedComponents(node, vecin);
}
} else {
lowestTime[node] = min(discoveryTime[vecin], lowestTime[node]);
}
}
}
int main() {
int n, m; in >> n >> m;
G.resize(n + 1); discoveryTime.resize(n + 1); discoveryTime.assign(n + 1, -1); lowestTime.resize(n + 1);
for(int i = 1; i <= m; ++i) {
int x, y; in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1, 0, 0);
out << (int)componenteBiconexe.size() << '\n';
for(int i = 0; i < (int)componenteBiconexe.size(); ++i) {
map< int, bool > printed;
for(int j = 0; j < (int)componenteBiconexe[i].size(); ++j) {
if(!printed[componenteBiconexe[i][j]]) {
out << componenteBiconexe[i][j] << " ";
printed[componenteBiconexe[i][j]] = true;
}
}
out << '\n';
printed.clear();
}
in.close(); out.close();
return 0;
}