Cod sursa(job #2433774)

Utilizator lucian2015blaugranadevil lucian2015 Data 28 iunie 2019 22:57:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#define nmax 100001


using namespace std;


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


class graf{
private:
	vector<int> edges[nmax];
	vector<int> tedges[nmax];
	vector<int> postorder;
	vector<bool> visited;
	vector<int>components;
	int num=0;
	int nodes=0;
public:
	graf(int n){
		nodes=n;
		visited.resize(nodes+1,0);
	//	postorder.resize(nodes+1,0);
		//components.resize(nodes+1,0);
	}
    void addedge(int x,int y){
    	edges[x].push_back(y);
    	tedges[y].push_back(x);
    }
    void dfs(int nod){
    	int i;
    	visited[nod]=1;
    	for(i=0;i<edges[nod].size();i++)
    		if(visited[edges[nod][i]]==0)
    			dfs(edges[nod][i]);
    	postorder.push_back(nod);
    }
    void dfst(int nod){
    	int i;
    	visited[nod]=0;
    	components.push_back(nod);
    	for(i=0;i<tedges[nod].size();i++)
    		 if(visited[tedges[nod][i]]==1)
    		 	dfst(tedges[nod][i]);
    }
 	void component(){
 		int i;
 		for(i=1;i<=nodes;i++)
 			if(visited[i]==0)
 				dfs(i);
 	    for(i=nodes-1;i>=0;i--){
 	    	
 			if(visited[postorder[i]]==1){
 				dfst(postorder[i]);
 				components.emplace_back(-1);
 				num++;
 			}
 		}
 		
 		g<<num<<"\n";
 		i=0;
 		for(i=0;i<components.size();i++){
 			if(components[i]==-1)
 				g<<"\n";
 			else
 			g<<components[i]<<" ";
 	}
 		
 	}

};
int main(){
 int n, m, x, y, i;
  f>>n>>m;
  graf graph(n);
for(i=1;i<=m;i++){
	f>>x>>y;
    graph.addedge(x,y);
}
	graph.component();
}