Cod sursa(job #2660703)

Utilizator smitoiStefan Mitoi smitoi Data 20 octombrie 2020 10:44:43
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

#define NMAX 100010
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

typedef struct {
    int index;
    int lowlink;
    bool onStack;
} nod;

vector<nod>     listaNoduri;
vector<int>     listaArce[NMAX];
vector<vector<int>>     listaComponente;
stack<int>      S;
int             n, m;
int             ix = 0;
int             k = 0;

void     strongconnect(int   v)
{
    listaNoduri[v].index = ix;
    listaNoduri[v].lowlink = ix;
    ix++;
    S.push(v);
    listaNoduri[v].onStack = true;

    for (int i = 0; i < listaArce[v].size(); i++)
    {
        int w = listaArce[v][i];
        if (listaNoduri[w].index == -1)
        {
            strongconnect(w);
            listaNoduri[v].lowlink = min(listaNoduri[v].lowlink, listaNoduri[w].lowlink);
        }
        else if (listaNoduri[w].onStack)
            listaNoduri[v].lowlink = min(listaNoduri[v].lowlink, listaNoduri[w].index);
    }

    if (listaNoduri[v].lowlink == listaNoduri[v].index)
    {
        k++;
        vector<int> L;
        int w;
        do {
            w = S.top();
            S.pop();
            listaNoduri[w].onStack = false;
            L.push_back(w);
        } while (v != w);
        listaComponente.push_back(L);
    }
    
}

// https://www.infoarena.ro/problema/ctc
// 
int		main()
{
	f >> n >> m;
	for (unsigned int i = 0; i < m; i++)
	{
		int nodS, nodD;
		f >> nodS >> nodD;
		listaArce[nodS].push_back(nodD);
	}

    for (unsigned int i = 1; i <= n + 1; i++)
        listaNoduri.push_back({-1, -1, false});
    
    for (unsigned int i = 1; i <= n; i++)
    {
        if (listaNoduri[i].index == -1)
            strongconnect(i);
    }
	
    cout << k << '\n';
    for (int i = 0; i < listaComponente.size(); i++)
    {
        for (int j = 0; j < listaComponente[i].size(); j++)
            cout << listaComponente[i][j] << ' ' ;
        cout << '\n';
    }

	return 0;
}