Pagini recente » Cod sursa (job #1184200) | Cod sursa (job #920421) | Cod sursa (job #2328954) | Cod sursa (job #951177) | Cod sursa (job #1810294)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
vector<int> BCC[MAX_N];
vector<int> G[MAX_N];
int low[MAX_N], dfn[MAX_N];
stack<pair<int,int>, vector<pair<int,int>>> stiva;
int N, M;
int NR_BCC;
void biconex(int x, int y){
NR_BCC++;
pair<int,int> p = {x, y}, q;
do{
q = stiva.top();
stiva.pop();
BCC[NR_BCC].push_back(q.first);
BCC[NR_BCC].push_back(q.second);
} while (p != q);
}
void dfs(int node, int nr){
dfn[node] = low[node] = nr;
for (int son : G[node]){
if (dfn[son] == 0){
stiva.push({node, son});
dfs(son, nr + 1);
low[node] = min(low[node], low[son]);
if (low[son] >= dfn[node]){
biconex(node, son);
}
}
else
low[node] = min(low[node], dfn[son]);
}
}
int main()
{
ifstream in("biconex.in");
ofstream out("biconex.out");
in >> N >> M;
for (int i = 0; i < M; i++){
int x, y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 1);
out << NR_BCC << "\n";
for (int i = 1; i <= NR_BCC; i++){
sort(BCC[i].begin(), BCC[i].end());
BCC[i].erase(unique(BCC[i].begin(), BCC[i].end()), BCC[i].end());
for (int x : BCC[i])
out << x << " ";
out << "\n";
}
return 0;
}