Pagini recente » Cod sursa (job #2746332) | Cod sursa (job #2353592) | Cod sursa (job #2666928) | Istoria paginii runda/eusebiu_oji_2017_cls11-12 | Cod sursa (job #2368709)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100002;
int task;
int N,M;
int x,y;
vector <int> Ad[NMAX];
vector <int> S;
vector <int> Comp[NMAX];
vector <pair<int,int> > m;
vector <int> Nc;
int nr_comp;
int ct;
int disc[NMAX];
int low[NMAX];
int index;
void DFS1(int nod,int parent)
{
disc[nod] = low[nod] = ++index;
for(int i=0;i<Ad[nod].size();++i)
{
int w=Ad[nod][i];
if(!disc[w])
{
S.push_back(w);
DFS1(w,nod);
low[nod]=min(low[nod],low[w]);
if(low[w]>=disc[nod])
{
nr_comp++;
S.push_back(nod);
while(!S.empty() && S.back()!=w )
{
Comp[nr_comp].push_back(S.back());
S.pop_back();
}
if(!S.empty())
{
Comp[nr_comp].push_back(S.back());
S.pop_back();
}
}
}
else if(w!=parent) low[nod]=min(low[nod],disc[w]);
}
}
void DFS2(int nod,int parent)
{
disc[nod] = low[nod] = ++index;
for(int i=0;i<Ad[nod].size();++i)
{
int w=Ad[nod][i];
if(!disc[w])
{
if(nod==1)ct++;
DFS2(w,nod);
low[nod]=min(low[nod],low[w]);
if(low[w]>=disc[nod] && nod!=1)
{
Nc.push_back(nod);
}
}
else if(w!=parent) low[nod]=min(low[nod],disc[w]);
}
}
void DFS3(int nod,int parent)
{
disc[nod] = low[nod] = ++index;
for(int i=0;i<Ad[nod].size();++i)
{
int w=Ad[nod][i];
if(!disc[w])
{
DFS3(w,nod);
low[nod]=min(low[nod],low[w]);
if(low[w]>disc[nod])
{
m.push_back(make_pair(nod,w));
}
}
else if(w!=parent) low[nod]=min(low[nod],disc[w]);
}
}
void Read()
{
//fin>>task;
task=1;
fin>>N>>M;
for(int i=1;i<=N;++i)
{
fin>>x>>y;
Ad[x].push_back(y);
Ad[y].push_back(x);
}
fin.close();
}
void Do()
{
if(task==1)
{
DFS1(1,0);
fout<<nr_comp<<"\n";
for(int i=1;i<=nr_comp;++i){fout<<Comp[i].size()<<" ";
for(int j=0;j<Comp[i].size();++j)
fout<<Comp[i][j]<<" ";fout<<"\n";}
}
if(task==2)
{
DFS2(1,0);
if(ct>=2)Nc.push_back(1);
fout<<Nc.size()<<"\n";
for(int i=0;i<Nc.size();++i)
fout<<Nc[i]<<" ";
}
if(task==3)
{
DFS3(1,0);
fout<<m.size()<<"\n";
for(int i=0;i<m.size();++i)fout<<m[i].first<<" "<<m[i].second<<"\n";
}
}
int main()
{
Read();
Do();
return 0;
}