Cod sursa(job #2198032)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 23 aprilie 2018 13:46:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

const int kNmax = 100005, ALB = 0, GRI = 1, NEGRU = 2;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	vector<int> adj[kNmax];
	vector<int> adjt[kNmax];
    stack<int> s;
    vector<int> cul;

	void read_input() {
		ifstream fin("ctc.in");
		fin >> n >> m;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			adjt[y].push_back(x);
		}
		fin.close();
	}
	void dfs(int nod) {
        cul[nod] = GRI;
        for(unsigned i = 0; i < adj[nod].size(); ++i)
            if(cul[ adj[nod][i] ] == ALB)
                dfs(adj[nod][i]);
        s.push(nod);
        cul[nod] = NEGRU;
	}
	void dfst(int nod, vector<int> &com) {
        cul[nod] = GRI;
        com.push_back(nod);
        for(unsigned i = 0; i < adjt[nod].size(); ++i)
            if(cul[ adjt[nod][i] ] == ALB)
                dfst(adjt[nod][i], com);
        cul[nod] = NEGRU;
	}
    void ctc(vector<vector<int> > &sol) {
        cul.resize(n + 1);
        for(int i = 1; i <= n; ++i)
            cul[i] = ALB;
        while(!s.empty()) {
            s.pop();
        }
        for(int i = 1; i <= n; ++i) {
            if(cul[i] == ALB)
                dfs(i);
        }
        for(int i = 1; i <= n; ++i)
            cul[i] = ALB;
        while(!s.empty()) {
            int nod = s.top();
            s.pop();
            if(cul[nod] == ALB) {
               vector<int> com;

                dfst(nod, com);
                sol.push_back(com);
            }

        }
    }
	vector<vector<int>> get_result() {
		/*
		TODO: Gasiti componentele tare conexe ale grafului orientat cu
		n noduri, stocat in adj. Rezultatul se va returna sub forma
		unui vector, ale carui elemente sunt componentele tare conexe
		detectate. Nodurile si componentele tare conexe pot fi puse in orice
		ordine in vector.

		Atentie: graful transpus este stocat in adjt.
		*/
		vector<vector<int>> sol;
		ctc(sol);
		return sol;
	}

	void print_output(vector<vector<int>> result) {
		ofstream fout("ctc.out");
		fout << result.size() << '\n';
		for (const auto& ctc : result) {
			for (int nod : ctc) {
				fout << nod << ' ';
			}
			fout << '\n';
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}