Pagini recente » Statistici Stefan Teau (StefanTeau) | Istoria paginii utilizator/matei_ionita | Cod sursa (job #1962719) | Cod sursa (job #2132764) | Cod sursa (job #781384)
Cod sursa(job #781384)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define NM 100010
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef pair<int, int> PI;
bool Equal (const PI& a, const PI& b)
{
return ((a.first==b.first && a.second==b.second) || (a.first==b.second && a.second==b.first));
}
vector<int> G[NM];
vector<int> ANS[NM];
stack<PI> S;
PI A,B;
int N,M,K,i,a,b;
int LVL[NM],D[NM];
void DF (int nod, int t)
{
D[nod]=LVL[nod];
for (unsigned int i=0; i<G[nod].size(); i++)
{
if (G[nod][i]==t) continue;
if (!LVL[G[nod][i]])
{
LVL[G[nod][i]]=LVL[nod]+1;
S.push(make_pair(G[nod][i],nod));
DF(G[nod][i],nod);
D[nod]=min(D[nod],D[G[nod][i]]);
if (D[G[nod][i]]>=LVL[nod])
{
++K;
B=make_pair(G[nod][i],nod);
if (!S.empty())
{
do
{
A=S.top();
S.pop();
ANS[K].push_back(A.first);
ANS[K].push_back(A.second);
}
while (!S.empty() && !Equal(A,B));
}
}
continue;
}
D[nod]=min(D[nod],D[G[nod][i]]);
}
}
int main ()
{
f >> N >> M;
for (i=1; i<=M; i++)
{
f >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for (i=1; i<=N; i++)
if (!LVL[i])
{
LVL[i]=1;
DF(i,0);
}
g << K << '\n';
for (i=1; i<=K; i++)
{
sort(ANS[i].begin(),ANS[i].end());
g << ANS[i][0] << ' ';
for (unsigned int j=1; j<ANS[i].size(); j++)
if (ANS[i][j]!=ANS[i][j-1])
g << ANS[i][j] << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}