Pagini recente » Cod sursa (job #1923118) | Cod sursa (job #1343747) | Cod sursa (job #398341) | Cod sursa (job #2190532) | Cod sursa (job #904450)
Cod sursa(job #904450)
#include<cstdio>
#include<cassert>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
int n, m, level, vis[100005], dp[100005], lvl[100005], bad_edg[200005];
vector<pair<int, int> > be, graph[100005];
void dfs_edg_crit(int x, int v, int dad){
++level;
lvl[x] = level;
dp[x] = 9000001;
vis[x] = 1;
for(int i = 0; i < graph[x].size(); ++i)
if(!vis[graph[x][i].f]){
dfs_edg_crit(graph[x][i].f, graph[x][i].s, x);
dp[x] = min(dp[x], dp[graph[x][i].f]);
}
else if(graph[x][i].s != v)
dp[x] = min(dp[x], lvl[graph[x][i].f]);
if(dp[x] >= lvl[x]){
bad_edg[v] = 1;
be.push_back(mp(x, dad));
}
--level;
}
int nr_comp, comp[100005];
vector<int> lel[100005];
void dfs(int x){
lel[nr_comp].push_back(x);
vis[x] = 1;
comp[x] = nr_comp;
for(int i = 0; i < graph[x].size(); ++i)
if(!bad_edg[graph[x][i].s] && !vis[graph[x][i].f])
dfs(graph[x][i].f);
}
int dad[100005];
vector<int> arb[100005];
void read(){
// assert(freopen("critice2.in", "r", stdin));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i){
int x, y;
scanf("%d%d", &x, &y);
graph[x].pb(mp(y, i));
graph[y].pb(mp(x, i));
}
dfs_edg_crit(1, 0, 0);
be.pop_back();
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i)
if(!vis[i]){
++nr_comp;
dfs(i);
if(lel[nr_comp].size() < 2){
--nr_comp;
lel[nr_comp + 1].clear();
}
}
for(int i = 0; i < be.size(); ++i){
arb[comp[be[i].f]].pb(comp[be[i].s]);
arb[comp[be[i].s]].pb(comp[be[i].f]);
++nr_comp;
lel[nr_comp].push_back(be[i].f);
lel[nr_comp].push_back(be[i].s);
}
}
double ans;
void solve(){
}
void write(){
//assert(freopen("critice2.out", "w", stdout));
// printf("%lf", ans);
printf("%d\n", nr_comp);
for(int i = 1; i <= nr_comp; ++i){
for(int j = 0; j < lel[i].size(); ++j)
printf("%d ", lel[i][j]);
printf("\n");
}
}
int main(){
assert(freopen("biconex.out", "w", stdout));
assert(freopen("biconex.in", "r", stdin));
read();
solve();
write();
return 0;
}