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