Cod sursa(job #1890534)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 23 februarie 2017 12:28:34
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

void DFS (unsigned int node, unsigned int father);

unsigned int N, M;
unsigned int x, y;

vector <unsigned int> G[100001];
stack < pair <unsigned int, unsigned int> > ST;
unsigned int idx[100001], mini[100001];
unsigned int i, j;

unsigned int solution;
vector <unsigned int> sol[100001];

int main ()
{
    fin >> N >> M;
    for(i=1; i<=M; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1,0);
    fout << solution << '\n';
    for (i=1; i<=solution; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
    return 0;
}

void DFS (unsigned int node, unsigned int father)
{
    unsigned int i;
    idx[node] = idx[father] + 1;
    mini[node] = idx[father] + 1;
    for (i=0; i<G[node].size(); i++)
        if (G[node][i] != father)
        {
            if (!idx[G[node][i]])
            {
                ST.push(make_pair(node,G[node][i]));
                DFS(G[node][i],node);
                if (mini[G[node][i]] >= idx[node])
                {
                    solution++;
                    do
                    {
                        x = ST.top().first;
                        y = ST.top().second;
                        ST.pop();
                        sol[solution].push_back(y);
                    } while (x != node && y != G[node][i]);
                    sol[solution].push_back(node);
                }
            }
            mini[node] = min(mini[node],mini[G[node][i]]);
        }
}