Pagini recente » Borderou de evaluare (job #1133772) | Cod sursa (job #1984188) | Cod sursa (job #1051116) | Cod sursa (job #2243773) | Cod sursa (job #530471)
Cod sursa(job #530471)
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define FOR(i, a, b) for(int i = a ; i <= b ; i++)
#define FORIT(it, V) for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define mp make_pair
#define fs first
#define sc second
const int NMAX = 100005;
int N, M;
vector<int> Graf[NMAX];
int lev[NMAX], jos[NMAX], tata[NMAX];
int viz[NMAX];//fac bitset
stack< pair<int, int> > ST;
int NR;
vector<int> sol[NMAX];
void citi()
{
scanf("%d%d", &N, &M);
FOR(i, 1, M)
{
int x, y;
scanf("%d%d", &x, &y);
Graf[x].push_back(y);
Graf[y].push_back(x);
}
}
void dfs(int nod)
{
viz[nod] = 1;
jos[nod] = lev[nod] = lev[tata[nod]] + 1;
FORIT(it, Graf[nod])
if(!viz[*it])
{
tata[*it] = nod;
ST.push(mp(nod, *it));
dfs(*it);
jos[nod] = min(jos[nod], jos[*it]);
if(jos[*it] >= lev[nod])
{
NR++;
while(!(ST.top() == mp(nod, *it)))
{
sol[NR].push_back(ST.top().fs);
sol[NR].push_back(ST.top().sc);
ST.pop();
}
sol[NR].push_back(ST.top().fs);
sol[NR].push_back(ST.top().sc);
ST.pop();
}
}
else if(tata[nod] != *it && lev[*it] < lev[nod])
{
jos[nod] = min(jos[nod], lev[*it]);
ST.push(mp(nod, *it));
}
}
void scrie()
{
printf("%d\n", NR);
FOR(i, 1, N)
{
sort(sol[i].begin(), sol[i].end());
sol[i].resize(unique(sol[i].begin(), sol[i].end()) - sol[i].begin());
FORIT(it, sol[i]) printf("%d ", *it);
printf("\n");
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citi();
dfs(1);
scrie();
return 0;
}