Pagini recente » Cod sursa (job #3122016) | Cod sursa (job #1215470) | Cod sursa (job #872947) | Cod sursa (job #1457558) | Cod sursa (job #499249)
Cod sursa(job #499249)
#include <cstdio>
#include <cstdlib>
#include <list>
#include <vector>
#include <utility>
using namespace std;
FILE *fin=fopen("biconex.in","r");
FILE *fout=fopen("biconex.out","w");
vector<int> v[100001];
int lvl[100001];
list< pair<int,int> > stk;
list< list<int> > res;
int unq[100001];
inline void unique(int n, int nr, list<int>& r)
{
if (unq[n]!=nr)
{
unq[n]=nr;
r.push_back(n);
}
}
void df(int n, int ln, int lv)
{
lvl[n]=lv;
stk.push_back(make_pair(ln,n));
for (vector<int>::iterator i=v[n].begin(); i!=v[n].end(); i++)
{
int ch = *i;
if (ch==ln) continue;
if ((lvl[ch])&&(lvl[ch]<lv))
{
list<int> r;
int nr = res.size()+1;
unique(n,nr,r);
unique(ch,nr,r);
while (stk.back().second!=ch)
{
unique(stk.back().first,nr,r);
unique(stk.back().second,nr,r);
stk.pop_back();
}
res.push_back(r);
}
if (!lvl[ch])
df(ch,n,lv+1);
}
if (stk.back()==make_pair(ln,n))
{
stk.pop_back();
if (ln!=0)
{
list<int> r;
r.push_back(ln);
r.push_back(n);
res.push_back(r);
}
}
}
void read_in()
{
FILE * fin = fopen("biconex.in","r");
int n,m;
fscanf(fin,"%d%d",&n,&m);
for (int i=0; i<m ; i++)
{
int x,y;
fscanf(fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
fclose(fin);
}
void write_out()
{
FILE * fout = fopen("biconex.out","w");
fprintf(fout,"%d\n",(int)res.size());
for (std::list< list<int> >::iterator i=res.begin(); i!=res.end(); i++)
{
for (std::list<int>::iterator j=(*i).begin(); j!=(*i).end(); j++)
fprintf(fout,"%d ",(*j));
fputc('\n',fout);
}
fclose(fout);
}
int main (int argc, char * const argv[]) {
read_in();
df(1,0,1);
write_out();
return 0;
}