Pagini recente » Cod sursa (job #2233956) | Cod sursa (job #2875399) | Cod sursa (job #1717854) | Cod sursa (job #1345356) | Cod sursa (job #1750124)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 100005;
vector<int> G[kMaxN];
namespace CBC {
vector<pair<int, int>> St;
int Parent[kMaxN], Time[kMaxN], Low[kMaxN];
vector<int> Nodes[kMaxN];
bool Viz[kMaxN];
int Art[kMaxN];
int n, timer, cbc;
void Init(int nn) {
n = nn;
for(int i = 1; i <= n; ++i) {
Parent[i] = Time[i] = Low[i] = Viz[i] = Art[i] = 0;
Nodes[i].clear();
}
timer = cbc = 0;
St.clear();
}
void DFS(int node) {
Viz[node] = 1;
Time[node] = ++timer;
Low[node] = Time[node];
for(auto vec : G[node]) {
if(vec == Parent[node]) continue;
if(!Viz[vec]) {
Viz[vec] = 1;
Parent[vec] = node;
St.emplace_back(node, vec);
DFS(vec);
Low[node] = min(Low[node], Low[vec]);
if(Low[vec] >= Time[node]) {
cbc++;
while(true) {
auto p = St.back();
St.pop_back();
Nodes[cbc].push_back(p.second);
if(p.first == node)
break;
}
Nodes[cbc].push_back(node);
}
} else if(Low[vec] < Low[node]) {
Low[node] = Low[vec];
}
}
}
void MakeArticulationPoints() {
for(int i = 1; i <= cbc; ++i) {
for(auto node : Nodes[i])
Art[node] += 1;
}
for(int i = 1; i <= n; ++i)
Art[i] = (Art[i] >= 2);
}
};
using namespace CBC;
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n;
fin >> n;
Init(n);
int m;
fin >> m;
while(m--) {
int a, b;
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
DFS(1);
fout << cbc << endl;
for(int i = 1; i <= cbc; ++i, fout << '\n')
for(auto node : Nodes[i])
fout << node << " ";
return 0;
}