Cod sursa(job #2194384)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 13 aprilie 2018 09:40:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 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 Kosaraju {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	vector<int> adj[kNmax];
    vector<int> adjT[kNmax];
	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, vector<int> &cul, stack<int> &s) {
        cul[nod] = GRI;
        for(unsigned i = 0; i < adj[nod].size(); ++i) {
            int fiu = adj[nod][i];
            if(cul[fiu] == ALB) {
                dfs(fiu, cul, s);
            }
        }
        cul[nod] = NEGRU;
        s.push(nod);
    }
    void dfsT(int nod, vector<int> &cul, vector<int> &comp) {
        cul[nod] = GRI;
        comp.push_back(nod);
        for(unsigned i = 0; i < adjT[nod].size(); ++i) {
            int fiu = adjT[nod][i];
            if(cul[fiu] == ALB) {
                dfsT(fiu, cul, comp);
            }
        }

        cul[nod] = NEGRU;
    }
	vector<vector<int> > get_result() {
	    vector<vector<int> > sol;
		vector<int> cul(n + 1, ALB);
		stack<int> s;
        for(int i = 1; i <= n; ++i) {
            if(cul[i] == ALB) {
                dfs(i, cul, s);
            }
        }
        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> comp;
                dfsT(nod, cul, comp);
                sol.push_back(comp);
            }

        }
		return sol;
	}

	void print_output(vector<vector<int> > result) {
		ofstream fout("ctc.out");
		fout << result.size() << '\n';
		for(unsigned i = 0; i < result.size(); ++i) {
            for (unsigned j = 0; j < result[i].size(); j++) {
                fout << result[i][j] << (j == result[i].size() - 1 ? '\n' : ' ');
            }
		}

		fout.close();
	}
};

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