Pagini recente » Cod sursa (job #973916) | Cod sursa (job #525545) | Cod sursa (job #1746750) | Cod sursa (job #1931341) | Cod sursa (job #2113008)
#include<bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100000;
vector<pair<int,int>> G[NMAX+2], GP[NMAX+2], init[NMAX+2];
bool viz[NMAX+2];
int ctc[NMAX+2], ind_ctc = 0, special_comp[NMAX+2];
vector<int> order, my_comp;
vector<pair<int,int>> adia[NMAX+2];
int artifact[NMAX+2];
int N, M;
vector<vector<int>> sol;
void dfs_plus(int nod)
{
viz[nod] = 1;
for( auto pp : G[nod] ) {
int x = pp.first;
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 pp : GP[nod] ) {
int x = pp.first;
if( viz[x] ) continue;
dfs_minus(x);
}
}
void DFS(int nod, int gasit = 0, int tata = -1)
{
gasit |= special_comp[nod];
artifact[nod] = gasit;
for( auto pp : adia[nod] ) {
int x = pp.first;
int z = pp.second;
if( x == tata ) continue;
DFS( x, gasit | z, nod );
}
}
int main()
{
in >> N >> M;
for( int i = 1; i <= M; ++i ) {
int x,y,z = 0;
in >> x >> y;
init[x].push_back({y,z});
init[y].push_back({x,z});
}
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 edg : G[i] ) {
int x = edg.first;
int z = edg.second;
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;
}