Mai intai trebuie sa te autentifici.
Cod sursa(job #2461679)
Utilizator | Data | 25 septembrie 2019 22:31:48 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.38 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
vector<int> v[100500];
bool vis[100500];
int disc[100500];
int low[100500];
int dCount;
struct edge
{
int x,y;
};
stack<edge> s;
int rezC;
vector<int> rez[100500];
void specDFS(int nodR, int fath)
{
vis[nodR]=true;
disc[nodR]=low[nodR]=dCount;
dCount++;
for(vector<int>::iterator i=v[nodR].begin();i!=v[nodR].end();++i)
{
int elem= *i;
if(fath==elem) continue;
if(!vis[elem])
{
s.push({nodR,elem});
specDFS(elem,nodR);
low[nodR]=min(low[nodR],low[elem]);
if(low[elem]>=disc[nodR])
{
while((s.top().x)!=nodR)
{
rez[rezC].push_back(s.top().y);
s.pop();
}
rez[rezC].push_back(s.top().y);
s.pop();
rez[rezC].push_back(nodR);
rezC++;
}
}
else
low[nodR]=min(low[nodR],disc[elem]);
}
}
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
int j,k;
fin>>j>>k;
v[j].push_back(k);
v[k].push_back(j);
}
for(int i=1;i<=n;i++)
if(!vis[i]) specDFS(i,0);
fout<<rezC<<"\n";
for(int i=0;i<rezC;i++)
{
sort(rez[i].begin(),rez[i].end());
for(vector<int>::iterator j=rez[i].begin();j!=rez[i].end();++j)
fout<<(*j)<<" ";
fout<<"\n";
}
}