Cod sursa(job #2464598)

Utilizator aZvezdaAtanas Dimitrov aZvezda Data 28 septembrie 2019 17:25:11
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<stack>
using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

vector<int> nbrs[N];
int br = 0;
int index[N];
int lowLink[N];
stack<int> st;
bool inStack[N];
int compCount = 0;
vector<int> output;

void dfs(int currentV)
{
    index[currentV] = br;
    lowLink[currentV] = br;
    ++br;
    st.push(currentV);
    inStack[currentV] = true;

    for(int i = 0; i < nbrs[currentV].size(); ++i)
    {
        int nextV = nbrs[currentV][i];

        if(index[nextV] == -1)
        {
            dfs(nextV);
            lowLink[currentV] =
                min(lowLink[currentV], lowLink[nextV]);
        }
        else if(inStack[nextV])
        {
            /// TODO: check if lowLink works the same
            lowLink[currentV] =
                min(lowLink[currentV], index[nextV]);
        }
    }

    if(index[currentV] == lowLink[currentV])
    {
        //cout << "New SCC:\n";
        while(st.top() != currentV)
        {
            output.push_back(st.top() + 1);
            //cout << st.top() + 1 << " ";
            st.pop();
        }
        output.push_back(st.top() + 1);
        output.push_back(-1);
        //cout << st.top() + 1 << endl;
        st.pop();
        ++compCount;
    }
}

int main()
{
    ofstream myfile;
    myfile.open ("ctc.out");

    ifstream myFileIn;
    myFileIn.open ("ctc.in");

    int n;
    int m;
    myFileIn >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        int from, to;
        myFileIn >> from >> to;
        --from;
        --to;

        nbrs[from].push_back(to);
    }

    for(int i = 0; i < n; ++i)
    {
        index[i] = -1;
        lowLink[i] = -1;
    }

    for(int i = 0; i < n; ++i)
    {
        if(index[i] == -1)
        {
            dfs(i);
        }
    }

    myfile << compCount << endl;
    for(int i = 0; i < output.size(); ++i)
    {
        if(output[i] == -1)
        {
            myfile << endl;
        }
        else
        {
            myfile << output[i] << " ";
        }
    }

    return 0;
}