Pagini recente » Cod sursa (job #2357511) | Cod sursa (job #3231868) | Cod sursa (job #2329776) | Cod sursa (job #2909071) | Cod sursa (job #249707)
Cod sursa(job #249707)
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 100005
#define x first
#define y second
#define foreach(V) for(typeof V.begin() it = V.begin(); it != V.end(); ++it)
int N, M;
vector<int> C[MAX_N];
vector<int> G[MAX_N];
stack<pair<int, int> > S;
int dfn[MAX_N], low[MAX_N];
int Nrc;
void citire()
{
scanf("%d %d",&N, &M);
for(int i = 1; i <= M; ++i)
{
int x, y;
scanf("%d %d",&x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void search(int x, int y)
{
++Nrc;
vector <int> aux;
int tx, ty;
do
{
tx = S.top().x, ty = S.top().y;
S.pop();
aux.push_back(tx);
aux.push_back(ty);
}
while(tx != x || ty != y);
sort(aux.begin(), aux.end());
C[Nrc].push_back(aux[0]);
for(int i = 1; i != aux.size(); ++i)
if(aux[i] != aux[i-1])
C[Nrc].push_back(aux[i]);
}
void DF(int n, int ant, int nr)
{
dfn[n] = low[n] = nr;
foreach(G[n])
{
int nod = *it;
if(nod == ant) continue;
if(dfn[nod] == -1)
{
S.push(make_pair(n, nod));
DF(nod, n, nr+1);
low[n] = min(low[n], low[nod]);
if(low[nod] >= dfn[n])
search(n, nod);
}
else
low[n] = min(low[n], dfn[nod]);
}
}
int main()
{
freopen("biconex.in","rt",stdin);
freopen("biconex.out","wt",stdout);
citire();
memset(dfn, -1, sizeof dfn);
DF(1, 0, 0);
printf("%d\n",Nrc);
for(int i = 1; i <= Nrc; ++i)
{
foreach(C[i])
printf("%d ",*it);
printf("\n");
}
}