Cod sursa(job #1719918)

Utilizator delta_wolfAndrei Stoica delta_wolf Data 20 iunie 2016 17:55:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int> > graf;
struct Node
{
    int lowlink;
    int discover;
    int inStack;
};
vector<Node> nodes;
stack<int> s;
vector<vector<int> > comps;
int nrcomps;
int timp;
void tarjan(int i)
{
    nodes[i].discover = timp;
    nodes[i].lowlink = timp;
    timp++;
    s.push(i);
    nodes[i].inStack = 1;
    for (int k = 0; k < graf[i].size(); k++)
    {
        int neighbour = graf[i][k];
        if (nodes[neighbour].discover == -1)
        {
            tarjan(neighbour);
            nodes[i].lowlink = min(nodes[i].lowlink, nodes[neighbour].lowlink);
        }
        else
        {
            if (nodes[neighbour].inStack)
                //backedge
                nodes[i].lowlink = min(nodes[i].lowlink, nodes[neighbour].discover);

        }

    }
    if (nodes[i].lowlink == nodes[i].discover)
    {
        int u;
        do
        {
            u = s.top();
            s.pop();
            nodes[u].inStack = 0;
            comps[nrcomps].push_back(u);
        } while (u != i);
        nrcomps++;
    }
}
void getComponents()
{
    for (int i = 0; i < nodes.size(); i++)
    {
        nodes[i].discover = -1;
        nodes[i].inStack = 0;
    }
    for (int i = 1; i < nodes.size(); i++)
    {
        if (nodes[i].discover == -1)
        {
            tarjan(i);
        }
    }
}

void print()
{
    out << nrcomps << "\n";

    for (int i = 0; i < nrcomps; i++)
    {
        for (int j = 0; j < comps[i].size(); j++)
            out << comps[i][j] << " ";
        out << "\n";
    }
}
int main()
{
    int n, m;
    in >> n >> m;
    graf.resize(n+1);
    nodes.resize(n+1);
    comps.resize(n+1);
    nrcomps = 0;
    timp = 0;
    for (int i = 0; i < m; i++)
    {
        int x,y;
        in >> x >> y;
        graf[x].push_back(y);
    }
    getComponents();
    print();

}