Pagini recente » Cod sursa (job #1401663) | Cod sursa (job #2334774) | Cod sursa (job #1931609) | Cod sursa (job #19451) | Cod sursa (job #957885)
Cod sursa(job #957885)
#include <cstdio>
#include <vector>
using namespace std;
struct Edge{
long value, ind;
};
const long N = 100001, M = 200001, INF = 2e9;
long n, m, level [N], dp [N], lvl = -1, dad [N], bad [M], ord, num = 0;
bool used [N], used1 [N];
Edge temp;
vector <Edge> graph [N];
vector <long> sol [N];
void read (){
long i, x, y;
Edge temp;
scanf ("%ld%ld", &n, &m);
for (i = 1; i <= m; i ++){
scanf ("%ld%ld", &x, &y);
temp.value = y;
temp.ind = i;
graph [x].push_back (temp);
temp.value = x;
graph [y].push_back (temp);
}
}
void dfs (long x, long ind){
long i;
Edge temp;
used [x] = true;
level [x] = ++ lvl;
dp [x] = INF;
for (i = 0; i < graph [x].size (); ++ i){
temp = graph [x][i];
if (!used [temp.value]){
dad [temp.value] = x;
dfs (temp.value, temp.ind);
dp [x] = min (dp [x], dp [temp.value]);
}
else
if (dad [x] != temp.value)
dp [x] = min (dp [x], level [temp.value]);
}
if (dp [x] >= level [x]){
bad [ind] = 1;
if (dad [x] != 0){
sol [++ ord].push_back (dad [x]);
sol [ord].push_back (x);
}
} // critica dad [x], x
lvl --;
}
void componente_conexe (long x){
long i;
Edge temp;
used1 [x] = 1;
sol [ord].push_back (x);
for (i = 0; i < graph [x].size (); i ++){
temp = graph [x][i];
if (!used1 [temp.value] && !bad [temp.ind])
componente_conexe (temp.value);
}
}
void solve (){
long i, g, j;
ord = 0;
for (i = 1; i <= n; i ++)
if (!used [i]){
dfs (i, 0);
}
for (i = 1; i <= n; i ++)
if (!used1 [i]){
ord ++;
componente_conexe (i);
if (sol [ord].size () == 1) {
sol [ord].clear ();
ord --;
}
}
printf ("%ld\n", ord);
for (i = 1; i <= ord; i ++){
for (j = 0; j < sol [i].size (); j ++)
printf ("%ld ",sol [i][j]);
printf ("\n");
}
}
int main (){
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
read ();
solve ();
return 0;
}