Pagini recente » Cod sursa (job #1387402) | Cod sursa (job #594608) | Cod sursa (job #985453) | Cod sursa (job #3190063) | Cod sursa (job #1690273)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int nmax = 1e5+5;
vector <int> g[nmax], comp[nmax];
bitset <nmax> viz;
stack <pair<int,int> > st;
int low[nmax], lev[nmax], nr;
void get_comp(int x, int y) {
int a, b;
nr++;
do {
a=st.top().first;
b=st.top().second;
comp[nr].push_back(b);
st.pop();
} while(a!=x || b!=y);
comp[nr].push_back(a);
}
void dfs(int dad) {
viz[dad]=true;
low[dad]=lev[dad];
for(auto son : g[dad]) {
if(viz[son]==false) {
lev[son]=lev[dad]+1;
st.push({dad, son});
dfs(son);
low[dad]=min(low[dad], low[son]);
if(low[son] >= lev[dad]) ///nodul 'dad' este critic
get_comp(dad, son);
}
else low[dad]=min(low[dad], lev[son]);
}
}
int main() {
ios_base::sync_with_stdio(false);
int i, x, y, n, m;
fin >> n >> m;
for(i=1; i<=m; i++) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
lev[1]=1;
dfs(1);
fout << nr << '\n';
for(i=1; i<=nr; i++) {
sort(comp[i].begin(), comp[i].end());
for(auto it : comp[i])
fout << it << " ";
fout << "\n";
}
return 0;
}