Cod sursa(job #2571085)

Utilizator natrovanCeval Marius natrovan Data 4 martie 2020 21:00:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define N 100005
int n, m, i, nrc, h[N], low[N], x, inaltime;
bitset<N> viz, eInStiva;
vector<int>L[N]; ///listele de adiacenta
vector<int>c[N]; ///componenetele tare conexe
stack<int>st;

void citireGraf(){
	int i, x, y;
	fin >> n >> m;
	for(i = 1; i <= m; i++){
		fin >> x >> y;
        	L[x].push_back(y);
	}
}

void dfs(int x) {
	int z;
	inaltime++; /// urc in stiva
	viz[x] = 1;
	low[x] = h[x] = inaltime;

	st.push(x);
	eInStiva[x] = 1;

	for(auto y : L[x]) {
        	if(viz[y] == 0){
			dfs(y);
			low[x] = min(low[x], low[y]);///actualizez cel mai jos punct in care pot ajunge din x
        	}
        	else if(eInStiva[y])
			low[x] = min(low[x], h[y]);
    	}

	///m-am intros intr-un punct sursa -- extrag componenta tare conexa
    	if (low[x] == h[x]){
 		nrc++;
        	do{
			z = st.top();
			st.pop();
			eInStiva[z] = 0;
            		c[nrc].push_back(z);
          	}while(z!=x);
     	}
}


int main() {

    citireGraf();
    for(i = 1; i <= n; i++)
        if(viz[i] == 0)
            dfs(i);

    ///afisez componentele tare conexe
    fout<< nrc << '\n';
    for(i = 1; i <= nrc; i++){
	for (auto x : c[i])
		fout << x <<' ';
                fout <<'\n';
    }

    fin.close(); fout.close();
    return 0;
}