Pagini recente » Cod sursa (job #2777404) | Cod sursa (job #407990) | Cod sursa (job #361308) | Cod sursa (job #1733719) | Cod sursa (job #2665024)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
using namespace std;
const int NMAX = 1e5;
// ---------- CITIRE ------------
vector <int> g[1 + NMAX];
vector <int> rasp[1 + NMAX];
int n, m;
void citire() {
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i ++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
}
// ---------- REZOLVARE ---------
int currentTime, dfsRoot, rootsNumberOfChildren, nrComponenteBiconexe;
int discoverTime[1 + NMAX], lowLink[1 + NMAX], dfsParent[1 + NMAX];
bool isArticulationPoint[1 + NMAX];
stack <pair<int, int>> myStack;
void ArticulationPointsDFS(int from) {
discoverTime[from] = lowLink[from] = ++currentTime;
for(auto &to: g[from]) {
if(discoverTime[to] == 0) {
dfsParent[to] = from;
if(from == dfsRoot) ++rootsNumberOfChildren;
myStack.push(make_pair(from, to));
ArticulationPointsDFS(to);
if(lowLink[to] >= discoverTime[from]) {
isArticulationPoint[from] = true;
while(myStack.top().first != from || myStack.top().second != to) {
rasp[nrComponenteBiconexe].push_back(myStack.top().first);
rasp[nrComponenteBiconexe].push_back(myStack.top().second);
myStack.pop();
}
rasp[nrComponenteBiconexe].push_back(from);
rasp[nrComponenteBiconexe].push_back(to);
myStack.pop();
nrComponenteBiconexe ++;
}
lowLink[from] = min(lowLink[from], lowLink[to]);
} else {
/// De repetat asta
if(to != dfsParent[from]) {
lowLink[from] = min(lowLink[from], lowLink[to]);
if(discoverTime[to] < discoverTime[from]) {
myStack.push(make_pair(from, to)); /// HMMMMMM
}
}
}
}
}
void solve() {
for(int i = 1; i <= n; i ++) {
if(discoverTime[i] == 0) {
dfsRoot = i;
rootsNumberOfChildren = 0;
ArticulationPointsDFS(dfsRoot);
isArticulationPoint[dfsRoot] = (rootsNumberOfChildren > 1);
if(myStack.empty() == false) {
while(!myStack.empty()) {
rasp[nrComponenteBiconexe].push_back(myStack.top().first);
rasp[nrComponenteBiconexe].push_back(myStack.top().second);
myStack.pop();
}
nrComponenteBiconexe ++;
}
}
}
}
// ---------- AFISARE -----------
void afisare() {
printf("%d\n", nrComponenteBiconexe);
for(int i = 0; i < nrComponenteBiconexe; i ++) {
sort(rasp[i].begin(), rasp[i].end());
rasp[i].erase(unique(rasp[i].begin(), rasp[i].end()), rasp[i].end());
for(auto &nod: rasp[i]) {
printf("%d ", nod);
}
printf("\n");
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citire();
solve();
afisare();
return 0;
}