Cod sursa(job #2122433)

Utilizator alexandru822Bosinta Alexandru alexandru822 Data 5 februarie 2018 07:48:32
Problema Componente biconexe Scor 48
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int N_MAX = 100000;
vector<int> neighbours[1 + N_MAX], curcomp;
vector<vector<int>> components;
int n, depth[1 + N_MAX], height[1 + N_MAX], dad[1 + N_MAX];
bool visited[1 + N_MAX];

void read()
{
    int m;
    in >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        neighbours[x].push_back(y);
        neighbours[y].push_back(x);
    }
    depth[1] = 1;
    height[1] = 1;
}

void dfs(int node)
{
    for(int m : neighbours[node])
    {
        if(dad[node] == m)
            continue;
        if(depth[m])
            height[node] = min(height[node], height[m]);
        else
        {
            dad[m] = node;
            depth[m] = depth[node] + 1;
            height[m] = depth[m];
            dfs(m);
            height[node] = min(height[node], height[m]);
        }
    }
}

void findcomponents(int node)
{
    curcomp.push_back(node);
    visited[node] = true;
    for(int m : neighbours[node])
    {
        if(visited[m])
            continue;
        if(depth[node] <= height[m] & curcomp.size() != 1)
        {
            components.push_back(curcomp);
            curcomp.clear();
            curcomp.push_back(node);
        }
        findcomponents(m);
    }
}

void print()
{
    out << components.size() + 1 << "\n";
    for(vector<int> m : components)
    {
        for(int r : m)
            out << r << " ";
        out << "\n";
    }
    for(int m : curcomp)
        out << m << " ";
}

int main()
{
    read();
    dfs(1);
    findcomponents(1);
    print();
    return 0;
}