Pagini recente » Cod sursa (job #1794815) | Cod sursa (job #2345565) | Cod sursa (job #3213555) | Cod sursa (job #1915333) | Cod sursa (job #833320)
Cod sursa(job #833320)
#include<stdio.h>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
#define maxn 100100
stack <int> stiva;
vector <int> vec[maxn];
vector <int> comp[maxn];
int N, M, nr = 0;
int sel[maxn];
int tata[maxn];
int df(int nod, int h) {
stiva.push(nod);
sel[nod] = h;
for( size_t i = 0; i < vec[nod].size(); ++i) {
int val;
if( vec[nod][i] == tata[nod] ) continue;
if( sel[ vec[nod][i]] == 0) {
tata[vec[nod][i]] = nod;
df(vec[nod][i], h + 1);
if( sel[vec[nod][i]] >= sel[nod] ) {
while( stiva.top() != nod) {
comp[nr].push_back(stiva.top());
stiva.pop();
}
comp[nr].push_back(stiva.top());
sort(comp[nr].begin(), comp[nr].end());
nr++;
}
}
val = sel[vec[nod][i]];
if( sel[nod] > val)
sel[nod] = val;
}
return sel[nod];
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &N, &M);
for( int i = 1; i <= M; ++i) {
int a, b;
scanf("%d %d", &a, &b);
vec[a].push_back(b);
vec[b].push_back(a);
}
for( int i = 1; i <= N; ++i) {
if( sel[i] == 0)
df(i, 0);
}
nr--;
cout<< nr<<endl;
for( int j = 0; j < nr; ++j) {
for( size_t i = 0; i < comp[j].size(); ++i)
cout<< comp[j][i]<<" ";
cout<<endl;
}
return 0;
}