Cod sursa(job #1904383)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 5 martie 2017 15:11:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");

const int Dim = 100002;
int N, M ,sp ,sol;
vector<vector<int>> G;
stack<pair<int,int>> st;
vector <int> T,index,L;
set<int> comp[Dim];

void Read_Graph()
{
int x,y;
fi>>N>>M;
G.resize(N+1);
L.resize(N+1);
index.resize(N+1);
T.resize(N+1);
for (int i = 1;i <= M; ++i)
    {
        fi>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

}

void Write()
{
fo<<sol<<'\n';
for (int i = 1; i <= sol; ++i,fo<<'\n')
    for (auto y : comp[i])
            fo<<y<<" ";
}

void Comp_biconexe(int x)
{

    L[x] = index[x];
    for (const int& y : G[x])
    {
		if ( y == T[x]) continue;
        if (index[y]==0)
            { T[y] = x;
              index[y] = index[x] + 1;

              st.push({x, y});
              Comp_biconexe(y);
              L[x] = min(L[x], L[y]);

            if (L[y] >= index[x])
            {
                ++sol;
                pair<int,int> p;
               do {
                     p = st.top();
                    st.pop();
                    comp[sol].insert(p.first);
                    comp[sol].insert(p.second);
                  }
                  while  (! ( p.first == x && p.second == y));
            }
        }
        else	L[x] = min(L[x], index[y]);
	}
}

int main()
{
Read_Graph();
Comp_biconexe(1);
Write();
}