Pagini recente » Cod sursa (job #2894451) | Cod sursa (job #1786742) | Cod sursa (job #3307616) | Cod sursa (job #3330829) | Cod sursa (job #3347663)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
using namespace std;
const int oo = 0x3f3f3f3f;
vector<vector<int>> G;
vector<set<int>> BCC;
vector<int> dfn,low,Art;
stack<pair<int,int>> S;
int N,M,nr_fii = 0,num = 0,nrBCC = 0,start;
void read()
{
fin >> N >> M;
G.resize(N+1);
BCC.resize(N+1);
dfn.resize(N+1,-1);
low.resize(N+1,oo);
Art.resize(N+1,0);
int x,y;
for(int i = 1; i <= M; ++i)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Build_BCC(int x,int y)
{
++nrBCC;
pair<int,int> crt;
do
{
crt.first = S.top().first;
crt.second = S.top().second;
S.pop();
BCC[nrBCC].insert(crt.first);
BCC[nrBCC].insert(crt.second);
}while(crt.first != x || crt.second != y);
}
void DFSBCC(int nod_s,int nod_t)
{
dfn[nod_s] = low[nod_s] = ++num;
for(auto vecin : G[nod_s])
{
if(vecin != nod_t && dfn[vecin] < dfn[nod_s])
S.push({vecin,nod_s});
if(dfn[vecin] == -1)
{
if(nod_s == start)
nr_fii++;
DFSBCC(vecin,nod_s);
low[nod_s] = min(low[nod_s],low[vecin]);
if(low[vecin] >= dfn[nod_s])
{
if(nod_s != start)
Art[nod_s] = 1;
Build_BCC(vecin,nod_s);
}
}
else
if(vecin != nod_t)
low[nod_s] = min(low[nod_s],low[vecin]);
}
}
int main()
{
ios::sync_with_stdio(false);
fin.tie(0);
read();
start = 1;
DFSBCC(1,-1);
if(nr_fii > 1)
Art[start] = 1;
if(nrBCC == 0)
{
++nrBCC;
pair<int,int> crt;
while(!S.empty())
{
crt.first = S.top().first;
crt.second = S.top().second;
S.pop();
BCC[nrBCC].insert(crt.first);
BCC[nrBCC].insert(crt.second);
}
}
fout << nrBCC << '\n';
for(int i = 1; i <= nrBCC; ++i)
{
for(auto elem : BCC[i])
fout << elem << ' ';
fout << '\n';
}
}