Cod sursa(job #1283299)

Utilizator PhilipDumitruPhilip Dumitru PhilipDumitru Data 5 decembrie 2014 15:05:05
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <stack>
#include <list>
#include <queue>

using namespace std;

list<int> adiacList[100001];
int index[100001], idx;
int lowlink[100001];
int convCounter;
short isInStack[100001];
queue<int> printQue;
stack<int> st;

void tarjan(int x)
{
    index[x] = idx;
    lowlink[x] = idx++;
    st.push(x);
    isInStack[x] = 1;

    list<int>::iterator it, it_end = adiacList[x].end();
    for (it = adiacList[x].begin(); it != it_end; ++it)
    {
        if (!index[*it])
        {
            tarjan(*it);
            lowlink[x] = (lowlink[x] < lowlink[*it]) ? lowlink[x] : lowlink[*it];
        }
        else if (isInStack[*it])
        {
            lowlink[x] = (lowlink[x] < index[*it]) ? lowlink[x] : index[*it];
        }
    }
    int y;
    if (index[x] == lowlink[x])
    {
        do
        {
            y = st.top();
            st.pop();
            isInStack[y] = 0;
            printQue.push(y);
        }
        while (y != x);
        printQue.push(0);
        ++convCounter;
    }
}

int main()
{
    FILE * fin = fopen("ctc.in", "r");
    FILE * fout = fopen("ctc.out", "w");

    int n, m, i, j;
    fscanf(fin, "%d %d", &n, &m);
    while (m--)
    {
        fscanf(fin, "%d %d", &i, &j);
        adiacList[i].push_back(j);
        //adiacList[j].push_back(i);
    }

    for (i = 1; i <= n; ++i)
    {
        if (!index[i])
            tarjan(i);
    }
    fprintf(fout, "%d\n", convCounter);
    while (!printQue.empty())
    {
        i = printQue.front();
        printQue.pop();
        if (i)
            fprintf(fout, "%d ", i);
        else
            fprintf(fout, "\n");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}