Pagini recente » Cod sursa (job #380299) | Cod sursa (job #2720054) | Cod sursa (job #1420984) | Cod sursa (job #2525333) | Cod sursa (job #1521904)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int nmax = 100050;
vector <int> graf[nmax], componente[nmax];
int F[nmax], Stk[nmax], howHigh[nmax], lvl[nmax], nrComp, n, m;
void DFS(int poz){
F[poz] = true;
Stk[ ++Stk[0] ] = poz;
howHigh[poz] = lvl[poz];
for(int node = 0; node < graf[poz].size(); ++node ){
if( !F[ graf[poz][node] ] ){
lvl[ graf[poz][node] ] = lvl[poz] + 1;
DFS( graf[poz][node] );
howHigh[poz] = min( howHigh[poz], howHigh[ graf[poz][node] ] );
if(howHigh[ graf[poz][node] ] >= lvl[poz]){
++nrComp;
while( Stk[ Stk[0] + 1 ] != graf[poz][node]){
componente[ nrComp ].push_back( Stk[Stk[0]--] );
}
componente[ nrComp ].push_back( poz );
}
}
else if( lvl[poz] > lvl[ graf[poz][node] ] )
howHigh[poz] = min(howHigh[ poz ], lvl[ graf[poz][node] ]);
}
}
int main()
{
f>>n>>m;
for(int i = 1, x, y; i <= m; ++i){
f>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for(int i = 1; i <= n; ++i){
if( !F[i] ){
DFS(i);
}
}
g<<nrComp<<'\n';
for(int i = 1; i <= nrComp; ++i){
for( int j = 0; j < componente[i].size(); ++j )
g<< componente[i][j] <<' ';
g<<'\n';
}
return 0;
}