Pagini recente » Istoria paginii utilizator/gabriela.tpc | Istoria paginii utilizator/cristina_16 | Istoria paginii runda/prega_casi_5.12.2018/clasament | Cod sursa (job #1296449) | Cod sursa (job #754976)
Cod sursa(job #754976)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define nmax 100110
#define from first
#define to second
vector<int> G[nmax], c;
stack<pair<int, int> > S;
vector<vector<int> > C;
int N, M, x, y, niv[nmax], low[nmax];
void Comp(int x, int y)
{
c.clear();
pair<int, int> p;
do
{
p = S.top();
S.pop();
c.pb(p.to);
}while(p.from != x && p.to != y);
c.pb(p.from);
C.pb(c);
}
void DFS(int nod, int t = 0)
{
low[nod] = niv[nod];
vector<int> :: iterator it;
for(it = G[nod].begin(); it != G[nod].end(); ++it)
{
if(*it == t) continue;
if(!niv[*it])
{
S.push(mp(nod, *it));
niv[*it] = niv[nod] + 1;
DFS(*it, nod);
low[nod] = min(low[nod], low[*it]);
if(low[*it] >= niv[nod])
Comp(nod, *it);
}else
{
low[nod] = min(low[nod], low[*it]);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int i, j;
scanf("%i %i", &N, &M);
for(i = 0; i < M; i++)
{
scanf("%i %i", &x, &y);
G[x].pb(y);
G[y].pb(x);
}
for(i = 1; i <= N; i++)
{
if(!niv[i])
{
niv[i] = 1;
DFS(i);
}
}
printf("%i\n", C.size());
for(i = 0; i < C.size(); i++)
{
for(j = 0; j < C[i].size(); j++)
printf("%i ", C[i][j]);
printf("\n");
}
scanf("%i", &i);
return 0;
}