Pagini recente » Cod sursa (job #2880119) | Cod sursa (job #1167387) | Cod sursa (job #1591169) | Cod sursa (job #2390626) | Cod sursa (job #2802293)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int const N = 2e5 + 3 , L = 1e6;
ofstream g ("biconex.out");
vector <int> v [N] ;
vector <pii> cc [N];
stack <pii> st;
int h [N] , c1 , viz [N] , cn [N] , p;
char s [L];
int dfs (int node){
int ans (h [node] + 1);
for(auto y : v [node]){
if (h [y] <= h [node])
st.push (mp (node , y));
if (h [y]){
ans = min (ans , h [y]);
continue;
}
h [y] = 1 + h [node];
int x = dfs (y);
ans = min (ans , x);
if (x >= h [node]){
++ c1;
while (st.size () && st.top () != mp (node , y)){
cc [c1].push_back (st.top ());
st.pop ();
}
cc [c1].push_back (mp (node , y));
st.pop ();
}
}
return ans;
}
int nextInt (){
int r (0);
while (! isdigit (s [p])){
++ p;
if (p == L){
fread (s , 1 , L , stdin);
p = 0;
}
}
while (isdigit (s [p])){
r = r * 10 + (s [p] - '0');
++ p;
if (p == L){
fread (s , 1 , L , stdin);
p = 0;
}
}
return r;
}
int n , m;
int main (){
freopen ("biconex.in" , "r" , stdin);
fread (s , 1 , L , stdin);
n = nextInt () , m = nextInt ();
for(int i = 1 ; i <= m ; ++ i){
int a , b;
a = nextInt () , b = nextInt ();
v [a].push_back (b);
v [b].push_back (a);
}
for(int i = 1 ; i <= n ; ++ i)
if (! h [i]){
h [i] = 1;
dfs (i);
}
g << c1 << '\n';
for(int i = 1 ; i <= c1 ; ++ i){
cn [0] = 0;
for(auto [x , y] : cc [i]){
cn [++ cn [0]] = x;
cn [++ cn [0]] = y;
}
sort (cn + 1 , cn + cn [0] + 1);
int l = unique (cn + 1 , cn + cn [0] + 1) - cn;
for(int i = 1 ; i < l ; ++ i)
g << cn [i] << ' ';
g << '\n';
}
return 0;
}