Pagini recente » Cod sursa (job #1308299) | Cod sursa (job #2308899) | Cod sursa (job #2226001) | Cod sursa (job #1450559) | Cod sursa (job #2409437)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int VAL=100005;
int N, M, i, j, A, B;
int st[VAL], top, low[VAL];
int NRCOMP, niv[VAL], X;
bool ok[VAL];
vector <int> G[VAL];
vector <int> COMP[VAL];
void DFS(int nod, int FAT)
{
vector <int> :: iterator it;
ok[nod]=true;
niv[nod]=low[nod]=niv[FAT]+1;
st[++top]=nod;
for (it=G[nod].begin(); it!=G[nod].end(); it++)
{
if (*it==FAT)
continue;
if (ok[*it]==true)
{
low[nod]=min(low[nod], niv[*it]);
continue;
}
DFS(*it, nod);
low[nod]=min(low[nod], low[*it]);
if (niv[nod]<=low[*it])
{
NRCOMP++;
while (top>0)
{
COMP[NRCOMP].push_back(st[top]);
if (st[top]==*it)
{
top--;
break;
}
top--;
}
COMP[NRCOMP].push_back(nod);
}
}
}
int main()
{
fin >> N >> M;
for (i=1; i<=M; i++)
{
fin >> A >> B;
G[A].push_back(B);
G[B].push_back(A);
}
for (i=1; i<=N; i++)
{
if (ok[i]==false)
{
//top=0;
DFS(i, 0);
}
}
fout << NRCOMP << '\n';
for (i=1; i<=NRCOMP; i++)
{
for (j=0; j<COMP[i].size(); j++)
fout << COMP[i][j] << " ";
fout << '\n';
}
fin.close();
fout.close();
return 0;
}