Pagini recente » Cod sursa (job #2887386) | Cod sursa (job #1572633) | Cod sursa (job #2416935) | Cod sursa (job #2848117) | Cod sursa (job #2481652)
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#define MAX 100001
using namespace std;
vector<int> graph[MAX];
vector<vector<int>>compB;
stack<pair<int, int>> stiva;
int up[MAX], low[MAX];
bool vizitat[MAX];
void cleanStack(pair<int, int> pairN)
{
vector<int> subgraf;
int nx, ny;
do
{
nx = stiva.top().first;
ny = stiva.top().second;
stiva.pop();
subgraf.push_back(nx);
subgraf.push_back(ny);
}while(nx != pairN.first || ny != pairN.second);
compB.push_back(subgraf);
}
void DFS(int nod, int father, int id)
{
up[nod] = low[nod] = id;
for(auto vecin : graph[nod])
{
if(vecin != father && !vizitat[vecin])
{
vizitat[vecin] = 1;
stiva.push({nod, vecin});
DFS(vecin, nod, id + 1);
low[nod] = min(low[nod], low[vecin]);
if(low[vecin] >= up[nod])cleanStack({nod, vecin});
}
else if(vecin != father && vizitat[vecin])
{
low[nod] = min(low[nod], up[vecin]);
}
}
}
int main()
{
int n, m, a, b, i;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> n >> m;
for(i = 1; i <= m; i++)
{
fin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
DFS(1, 0, 0);
fout << compB.size() << '\n';
for(auto subgraf : compB)
{
sort(subgraf.begin(), subgraf.end());
subgraf.erase(unique(subgraf.begin(), subgraf.end()), subgraf.end());
for(auto nod : subgraf)fout << nod << " ";
fout << '\n';
}
fin.close();
fout.close();
return 0;
}