Pagini recente » Cod sursa (job #1391408) | Cod sursa (job #3292410)
#include <bits/stdc++.h>
#define DIM 2000001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
stack <int> stk;
vector <int> G[DIM];
vector <int> ret[DIM];
int found[DIM], low[DIM], lvl[DIM];
int t, n, i, m, x, y, bcc;
void dfs(int node, int dad){
found[node] = 1;
low[node] = lvl[node] = ++t;
stk.push(node);
for(auto k : G[node]){
if(k == dad)
continue;
if(found[k])
low[node] = min(low[node], lvl[k]);
else {
dfs(k, node);
low[node] = min(low[node], low[k]);
if(lvl[node] <= low[k]){
++bcc;
while(k != stk.top()){
ret[bcc].push_back(stk.top());
stk.pop();
}
ret[bcc].push_back(stk.top());
stk.pop();
ret[bcc].push_back(node);
}
}
}
}
int main(){
fin >> n >> m;
while(m--){
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!found[i])
dfs(i, 0);
fout << bcc << "\n";
for(i=1;i<=bcc;i++, fout << "\n")
for(auto k : ret[i])
fout << k << " ";
}