Cod sursa(job #2434129)

Utilizator lucian2015blaugranadevil lucian2015 Data 30 iunie 2019 17:41:48
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <vector>
#define nmax 100001


using namespace std;



inline int next_int() {
    
    int n = 0;
    
    char c = getchar_unlocked();
    
    while (!('0' <= c && c <= '9')) {    
        c = getchar_unlocked();
    }    
    while ('0' <= c && c <= '9') {
        n = n * 10 + c - '0';
        c = getchar_unlocked();
    }
    return n;
    
}

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++;
 			}
 		}
 		
 		printf("%d\n", num);
 		i=0;
 		for(i=0;i<components.size();i++){
 			if(components[i]==-1)
 				printf("\n");
 			else
 			printf("%d ", components[i]);
 	}
 		
 	}

};
int main(){
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
 int n, m, x, y, i;
 	//ios::sync_with_stdio(false);
 	//f.tie(NULL);
 	//g.tie(NULL);
  n=next_int();
  m=next_int();
  graf graph(n);
for(i=1;i<=m;i++){
	x=next_int();
    y=next_int();
    graph.addedge(x,y);
}
	graph.component();
}