Pagini recente » Cod sursa (job #928394) | Cod sursa (job #2591919) | Cod sursa (job #205922) | Cod sursa (job #233916) | Cod sursa (job #757199)
Cod sursa(job #757199)
#include <stack>
#include <bitset>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
typedef pair<int, int> pr;
const int N_MAX=100011;
stack<pr> S;
bitset<N_MAX> was;
vector<int> G[N_MAX], CBC[N_MAX];
int index, cbcSize;
int dfsIndex[N_MAX], lowIndex[N_MAX];
inline int _min(int x, int y) {return x <= y ? x : y;}
inline void DFS(int x)
{
dfsIndex[x]=lowIndex[x]=++index;
vector<int>::const_iterator it=G[x].begin(), iend=G[x].end();
for(; it < iend; ++it)
if(0 == dfsIndex[*it])
{
S.push(pr(x, *it));
DFS(*it);
lowIndex[x]=_min(lowIndex[x], lowIndex[*it]);
if(lowIndex[*it] >= dfsIndex[x])
{
static pr y, z;
y.first=x; y.second=*it;
do {
z=S.top(); S.pop();
if(false == was.test(z.first))
CBC[cbcSize].push_back(z.first), was.set(z.first);
if(false == was.test(z.second))
CBC[cbcSize].push_back(z.second), was.set(z.second);
}while(y != z);
++cbcSize;
}
was&=0;
}
else lowIndex[x]=_min(lowIndex[x], dfsIndex[*it]);
}
int main()
{
int N, M, x, y, i;
ifstream in("biconex.in");
ofstream out("biconex.out");
for(in>>N>>M; M; --M)
{
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(x=1; x <= N; ++x)
if(0 == dfsIndex[x])
DFS(x);
out<<cbcSize<<'\n';
for(i=0; i < cbcSize; ++i)
{
copy(CBC[i].begin(), CBC[i].end(), ostream_iterator<int>(out, " "));
out<<'\n';
}
return EXIT_SUCCESS;
}