Pagini recente » Monitorul de evaluare | Profil L337_Krew | Cod sursa (job #408775) | Monitorul de evaluare | Cod sursa (job #680933)
Cod sursa(job #680933)
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int MaxN = 100001;
const char InFile[] = "biconex.in";
const char OutFile[] = "biconex.out";
int N,M,nrc,nod1,nod2,lvl[MaxN],viz[MaxN],Last[MaxN];
vector<int> G[MaxN],sol[MaxN];
stack< pair<int,int> > St;
int minim(int x,int y)
{
return x > y?y:x;
}
void DFS(int nod,int father)
{
viz[nod] = 1;
Last[nod] = lvl[nod];
vector<int>::iterator it,iend;
iend = G[nod].end();
for( it = G[nod].begin() ; it != iend ; ++it )
{
int fiu = *it;
if( !viz[fiu] )
{
lvl[fiu] = lvl[nod] + 1;
St.push(make_pair(nod,fiu));
DFS(fiu,nod);
Last[nod] = minim(Last[nod],Last[fiu]);
if( Last[fiu] >= lvl[nod] )
{
++nrc;
do
{
nod1 = St.top().first;
nod2 = St.top().second;
St.pop();
sol[nrc].push_back(nod1);
sol[nrc].push_back(nod2);
}
while( ( nod1 != nod || nod2 != fiu ) && (nod1 != fiu || nod2 != nod) );
}
}
else
if( fiu != father )
Last[nod] = minim(Last[nod],lvl[fiu]);
}
}
int main()
{
ifstream fin(InFile);
ofstream fout(OutFile);
fin >> N >> M;
int i,x,y;
for( int i = 0 ; i < M ; i++ )
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
lvl[1] = 1;
DFS(1,1);
fout << nrc << '\n';
for( i = 1; i <= nrc ; i++ )
{
sort(sol[i].begin(),sol[i].end());
vector<int>::iterator it,iend;
iend = sol[i].end();
for( it = sol[i].begin() ; it != iend ; ++it )
if( it == sol[i].begin() || *it != (*(it-1)) )
fout << *it << ' ';
fout << '\n';
}
fout.close();
return 0;
}