Pagini recente » Cod sursa (job #133760) | Cod sursa (job #1186031) | Cod sursa (job #2811529) | Cod sursa (job #2078228) | Cod sursa (job #2113010)
#include<bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100000;
map<pair<int,int>,bool> orient;
vector<int> G[NMAX+2], GP[NMAX+2], init[NMAX+2];
bool viz[NMAX+2];
int ctc[NMAX+2], ind_ctc = 0;
vector<int> order, my_comp;
int N, M;
vector<vector<int>> sol;
void dfs_1(int nod)
{
viz[nod] = 1;
for( auto x : init[nod] ) {
if( !orient[{nod,x}] )
orient[{nod,x}] = orient[{x,nod}] = 1,
G[nod].push_back(x),
GP[x].push_back(nod);
if( viz[x] ) continue;
dfs_1(x);
}
}
void dfs_plus(int nod)
{
viz[nod] = 1;
for( auto x : G[nod] ) {
if( viz[x] ) continue;
dfs_plus(x);
}
order.push_back(nod);
}
void dfs_minus(int nod)
{
viz[nod] = 1;
ctc[nod] = ind_ctc;
my_comp.push_back(nod);
for( auto x : GP[nod] ) {
if( viz[x] ) continue;
dfs_minus(x);
}
}
int main()
{
in >> N >> M;
for( int i = 1; i <= M; ++i ) {
int x,y;
in >> x >> y;
init[x].push_back(y);
init[y].push_back(x);
}
dfs_1(1);
for( int i = 1; i <= N; ++i ) init[i].clear();
memset(viz, 0, sizeof(viz));
for( int i = 1; i <= N; ++i ) {
if( !viz[i] )
dfs_plus(i);
}
memset(viz, 0, sizeof(viz));
reverse(order.begin(), order.end());
for( auto x : order ) {
if( !viz[x] ) {
++ind_ctc;
my_comp.clear();
dfs_minus(x);
if( my_comp.size() > 1 )
sol.push_back(my_comp);
}
}
for( int i = 1; i <= N; ++i ) {
for( auto x : G[i] ) {
if( ctc[x] == ctc[i] ) {
/// if( z ) special_comp[ ctc[x] ] = 1;
}
else {
///adia[ ctc[i] ].push_back({ ctc[x] ,z});
///adia[ ctc[x] ].push_back({ ctc[i] ,z});
sol.push_back({i, x});
}
}
}
out << sol.size() << '\n';
for( auto& ln : sol ) {
for( auto& x : ln ) out << x << ' ';
out << '\n';
}
return 0;
}