Pagini recente » Cod sursa (job #1533720) | Cod sursa (job #126626) | Cod sursa (job #140134) | Cod sursa (job #2637092) | Cod sursa (job #1521883)
#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(auto node: graf[poz] ){
if( !F[node] ){
lvl[node] = lvl[poz] + 1;
DFS(node);
howHigh[poz] = min( howHigh[poz], howHigh[node] );
if(howHigh[node] >= howHigh[poz]){
while( Stk[ Stk[0] + 1 ] == node){
++nrComp;
componente[ nrComp ].push_back( Stk[Stk[0]--] );
}
componente[ nrComp ].push_back( poz );
}
}
else if( howHigh[poz] > howHigh[node] )
howHigh[poz] = howHigh[node];
}
}
int main()
{
f>>n>>m;
g<<n<<' '<<m<<'\n';
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(1);
}
}
g<<nrComp<<'\n';
for(int i = 1; i <= nrComp; ++i){
for(auto j : graf[i] )
g<<j<<' ';
g<<'\n';
}
return 0;
}