Cod sursa(job #2120999)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 3 februarie 2018 10:55:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

const int Max = 100005;

vector <int> V[Max];
vector <int> Sol[Max];
stack <int> S;

int n, m;
int niv[Max];
int low[Max];
int nr;

void citire()
{
	in >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y;
		in >> x >> y;
		V[x].push_back(y);
		V[y].push_back(x);
	}
}

void dfs(int nod)
{
	low[nod] = niv[nod];
	S.push(nod);
	for(auto i : V[nod])
	{
		if(niv[i])
			low[nod]=min(low[nod],niv[i]);
		else
		{
			niv[i] = niv[nod] + 1;
			dfs(i);
			low[nod] = min(low[nod],low[i]);
            if(low[i] >= niv[nod])
            {
                Sol[nr].push_back(nod);
				int f;
                while(1)
                {
                    f = S.top();
                    Sol[nr].push_back(f);
                    S.pop();
                    if(f==i)
                        break;
                }
				nr++;
            }
		}
	}
}

void biconex()
{
	for(int i = 1; i <= n; i++)
        if(niv[i] == 0)
        {
            niv[i] = 1;
            dfs(i);
        }
}

int main()
{
	citire();
	biconex();
	for(int i = 0;i < nr; i++)
        sort(Sol[i].begin(),Sol[i].end());
    out << nr <<'\n';
    for(int i = 0; i < nr; i++)
    {
        for(auto j : Sol[i])
            out<<j<<' ';
        out<<'\n';
    }
	return 0;
}