Pagini recente » Cod sursa (job #1241397) | Cod sursa (job #1964739) | Cod sursa (job #2448430) | Cod sursa (job #1170875) | Cod sursa (job #1131390)
//Voi scoate Santa de 100 de puncte $$$
#include <stdio.h>
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <map>
using namespace std;
//input
int N, M, source, sink, mlc;
vector <int> G[50000];
//componente biconexe
int low[50000], ord[50000], vis_biconex[50000];
pair <int, int> st[50000];
vector <int> cbc[50500];
int timp = 0, cntBiconex = 0, cntSt = 0;
void read() {
//freopen("santa.in", "r", stdin);
//freopen("santa.out", "w", stdout);
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &N, &M);
for (int i = 1; i <= M; ++i) {
int xx, yy;
scanf("%d%d", &xx, &yy);
G[xx].push_back(yy);
G[yy].push_back(xx);
}
//scanf("%d%d%d", &source, &sink, &mlc);
}
void load_component(int xx, int yy) {
++cntBiconex;
map <int, bool> MP;
while (cntSt > 0) {
int curx = st[cntSt].first;
int cury = st[cntSt].second;
if (MP[curx] == 0) {
MP[curx] = 1;
cbc[cntBiconex].push_back(curx);
}
if (MP[cury] == 0) {
MP[cury] = 1;
cbc[cntBiconex].push_back(cury);
}
--cntSt;
if (curx == xx && cury == yy)
break;
}
}
void dfs_biconex(int nod) {
vector <int> :: iterator it;
vis_biconex[nod] = 1;
ord[nod] = low[nod] = ++timp;
for (it = G[nod].begin(); it != G[nod].end(); ++it)
if (!vis_biconex[*it]) {
st[++cntSt].first = nod; st[cntSt].second = *it;
dfs_biconex(*it);
if (low[*it] >= ord[nod])
load_component(nod, *it);
if (low[*it] < low[nod])
low[nod] = low[*it];
} else if (ord[*it] < low[nod])
low[nod] = ord[*it];
}
int main() {
read();
dfs_biconex(1);
printf("%d\n", cntBiconex);
for (int i = 1; i <= cntBiconex; ++i, printf("\n"))
for (vector <int> :: iterator it = cbc[i].begin(); it != cbc[i].end(); ++it)
printf("%d ", *it);
return 0;
}