Pagini recente » Cod sursa (job #2645114) | Cod sursa (job #2300007) | Cod sursa (job #653913) | Cod sursa (job #2036956) | Cod sursa (job #302959)
Cod sursa(job #302959)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define INPUT "biconex.in"
#define OUTPUT "biconex.out"
#define pb push_back
#define mp make_pair
const long NMAX = 100001;
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
long N, M;
long niv[ NMAX ], low[ NMAX ];
vector<long> List[ NMAX ];
vector< vector<long> > Final;
stack<pair<long, long > > stk;
inline long Min(long _X, long _Y)
{
if(_X < _Y) return _X;
return _Y;
}
void readData()
{
long Node1, Node2;
fscanf(fin, "%ld %ld", &N, &M);
for(long i = 1; i <= M; ++i)
{
fscanf(fin, "%ld %ld", &Node1, &Node2);
List[ Node1 ].pb(Node2);
List[ Node2 ].pb(Node1);
}
}
void component(long x, long y)
{
vector<long> tmp;
long node1, node2;
do{
node1 = stk.top().first;
node2 = stk.top().second;
stk.pop();
tmp.pb(node1);
tmp.pb(node2);
}while(x != node1 || y != node2);
Final.pb(tmp);
}
void DFS(long node, long father, long level)
{
vector<long>::iterator it;
niv[ node ] = low[ node ] = level;
for(it = List[ node ].begin(); it != List[ node ].end(); ++it)
{
if(*it == father) continue;
if(niv[ *it ] == -1)
{
stk.push(mp(node, *it));
DFS(*it, node, level+1);
low[ node ] = Min(low[ node ], low[ *it ]);
if(low[ *it ] >= niv[ node ])
component(node, *it);
}
else
low[ node ] = Min(low[ node ], niv[ *it ]);
}
}
void display()
{
vector<long>::iterator it;
fprintf(fout, "%ld\n", Final.size());
for(long i = 0; i < Final.size(); ++i)
{
sort(Final[ i ].begin(), Final[ i ].end());
Final[ i ].erase(unique(Final[ i ].begin(), Final[ i ].end()), Final[ i ].end());
for(it = Final[ i ].begin(); it != Final[ i ].end(); ++it)
fprintf(fout, "%ld ", *it);
fprintf(fout, "\n");
}
}
int main()
{
readData();
for(long i = 1; i <= N; ++i)
niv[ i ] = low[ i ] = -1;
DFS(1, 0, 0);
display();
fclose(fin);
fclose(fout);
return 0;
}