Pagini recente » Cod sursa (job #159309) | Cod sursa (job #2485905) | Cod sursa (job #2630267) | Cod sursa (job #223163) | Cod sursa (job #689013)
Cod sursa(job #689013)
#define nume "biconex"
#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<ctime>
#include<list>
#include<algorithm>
using namespace std;
//#define _PARSARE_
#ifdef _PARSARE_
//////////////////////////////////////////////////////////////
//parsarea citirii
//////////////////////////////////////////////////////////////
#define DIM 8192
char ax[DIM+16];
int idx;
//numere NATURALE:
inline void cit_uint(int &x)
{
x=0;
while(ax[idx]<'0' || ax[idx]>'9')
if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;
while(ax[idx]>='0' && ax[idx]<='9') {
x=x*10+ax[idx]-'0';
if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
}
}
//numere INTREGI:
inline void cit_int(int &x)
{
x=0;
while((ax[idx]<'0' || ax[idx]>'9') && (ax[idx]!='-'))
if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;
int neg=0;
if(ax[idx]=='-') {
neg=1;
if(++idx==DIM)fread(ax, 1, DIM, stdin),idx=0;
}
while(ax[idx]>='0' && ax[idx]<='9') {
x=x*10+ax[idx]-'0';
if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
}
if(neg) x=-x;
}
#else
ifstream fin (nume".in");
#endif //_PARSARE_
ofstream fout(nume".out");
//#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
//#endif
#define foreach(V) for(vector<int>::iterator it=V.begin(),stop=V.end();it!=stop;++it)
#define foreach_set(V) for(set<int>::iterator it=V.begin(),stop=V.end();it!=stop;++it)
int n;
int m;
vector<int> G[100000+10];
set<int> sol[100000+10];
bool viz[100000+10];
int min_lev[100000+10];
int idx=0,nr=0;
stack<pair<int,int> > st;
inline void addsol(int x, int y)
{
int tmpx=0,tmpy=0;
while(tmpx!=x || tmpy!=y)
{
tmpx=st.top().first;
tmpy=st.top().second;
st.pop();
sol[nr].insert(tmpx);
sol[nr].insert(tmpy);
}
++nr;
}
void df(int nod)
{
viz[nod]=true;
min_lev[nod]=idx++;
foreach(G[nod]) {
if(!viz[*it]) {
st.push(make_pair(nod,*it));
df(*it);
if(min_lev[*it]>=min_lev[nod]) { //muchie critica
addsol(nod,*it);
}
min_lev[nod]=min(min_lev[nod],min_lev[*it]);
} else
min_lev[nod]=min(min_lev[nod],min_lev[*it]);
}
}
int main()
{
#ifdef _PARSARE_
freopen(nume".in","r",stdin);
cit_uint(n);
#else
fin>>n>>m;
#endif
for(int i=0; i<m; ++i) {
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; ++i)
if(!viz[i])
df(i);
fout<<nr<<'\n';
for(int i=0;i<nr;++i,fout<<'\n')
foreach_set(sol[i])
fout<<*it<<' ';
fout.close();
return 0;
}