Pagini recente » Cod sursa (job #2561600) | Cod sursa (job #2514146) | Cod sursa (job #515705) | Cod sursa (job #1403165) | Cod sursa (job #1088305)
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<stack>
using namespace std;
FILE *in,*out;
//definitii
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
//functii
void dfs(int nod,int tata,int level);
void biconex(pii stop);
//constante
const int Nmax=(int) 1e5+1;
//variabile
int noduri,muchii;
int nod1,nod2;
int minlevel[Nmax];
vector<int> graf[Nmax];
stack<pii > st;
vector<set<int> > answer;
int main(void)
{
in=fopen("biconex.in","rt");
out=fopen("biconex.out","wt");
fscanf(in,"%d%d",&noduri,&muchii);
for(int i=1;i<=muchii;++i)
{
fscanf(in,"%d%d",&nod1,&nod2);
graf[nod1].pb(nod2);
graf[nod2].pb(nod1);
}
dfs(1,-1,1);
fprintf(out,"%d\n",answer.size());
vector<set<int> > :: iterator it,end=answer.end();
for(it=answer.begin() ; it!=end ; ++it)
{
set<int> :: iterator sit,send=it->end();
for(sit=it->begin() ; sit!=send ; ++sit)
fprintf(out,"%d ",*sit);
fprintf(out,"\n");
}
fclose(in);
fclose(out);
return 0;
}
void dfs(int nod,int tata,int level)
{
minlevel[nod]=level;
vector<int> :: iterator it,end=graf[nod].end();
for(it=graf[nod].begin() ; it!=end ; ++it)
{
if(*it==tata)
continue;
if(minlevel[*it])
{
minlevel[nod]=min(minlevel[nod],minlevel[*it]);
continue;
}
st.push(mp(nod,*it));
dfs(*it,nod,level+1);
minlevel[nod]=min(minlevel[nod],minlevel[*it]);
if(level<=minlevel[*it])
biconex(mp(nod,*it));
}
}
void biconex(pii stop)
{
set<int> temp;
pii curent;
do
{
curent=st.top();
st.pop();
temp.insert(curent.first);
temp.insert(curent.second);
}
while(curent!=stop);
answer.pb(temp);
temp.clear();
}