Pagini recente » Cod sursa (job #1619503) | Cod sursa (job #380331) | Cod sursa (job #1265170) | Cod sursa (job #1305595) | Cod sursa (job #694332)
Cod sursa(job #694332)
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#define infile "biconex.in"
#define outfile "biconex.out"
#define n_max 100005
#define pb push_back
#define mkp make_pair
#define pii pair <int, int>
#define it_int vector < int > ::iterator
#define nxt *it
#define FOR(g) \
for(it_int it=g.begin(); it!=g.end(); ++it)
using namespace std;
vector < int > v[n_max];
stack < pii > ST;
vector < int > sol[n_max];
int dfn[n_max], low[n_max];
int N, M, Nrc;
void citeste()
{
freopen(infile, "r", stdin);
int x,y;
scanf("%d %d", &N, &M);
while(M--){
scanf("%d %d",&x, &y);
v[x].pb(y);
v[y].pb(x);
}
fclose(stdin);
}
void extrage(int x, int y)
{
pii edge;
Nrc++;
do{
edge = ST.top();
ST.pop();
sol[Nrc].pb(edge.first);
sol[Nrc].pb(edge.second);
} while(edge.first !=x || edge.second !=y);
sort(sol[Nrc].begin(), sol[Nrc].end());
it_int it = unique(sol[Nrc].begin(), sol[Nrc].end());
sol[Nrc].resize(it - sol[Nrc].begin());
}
void DFS(int x, int tx, int h)
{
dfn[x] = h;
low[x] = h;
FOR(v[x])
if(nxt != tx){
if(!dfn[nxt])
{
ST.push(mkp(x,nxt));
DFS(nxt, x, h+1);
low[x] = min(low[x],low[nxt]);
if(dfn[x] <= low[nxt])
extrage(x, nxt);
}
else
if(dfn[nxt] < dfn[x]){
ST.push(mkp(x,nxt));
low[x] = min(low[x],low[nxt]);
}
}
}
void afiseaza()
{
freopen(outfile, "w", stdout);
printf("%d\n", Nrc);
for(int i=1; i<= Nrc;++i){
FOR(sol[i])
printf("%d ", nxt);
printf("\n");
}
fclose(stdout);
}
int main()
{
citeste();
DFS(1,0,1);
afiseaza();
return 0;
}