Cod sursa(job #2251858)

Utilizator b10nd3Oana Mancu b10nd3 Data 2 octombrie 2018 02:48:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb

//Tarjan

#include<iostream>
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

vector <int> idx, lowLink, inStack;
vector <vector<int> > rez;
stack<int> S;
int indecs;

void Tarjan(int v, vector<int> *adj){
	idx[v]=lowLink[v]=indecs;
	inStack[v]=1; S.push(v);
	indecs++;
	
	vector <int> :: const_iterator it;
	for( it = adj[v].begin(); it != adj[v].end(); it++){
		if(idx[*it]==-1){
			Tarjan(*it,adj);
			lowLink[v]=min(lowLink[v],lowLink[*it]);
		}
		else if(inStack[*it]==1)
		    lowLink[v]=min(lowLink[v],lowLink[*it]);
	}

    
    //componenta tare conexa formata
    if(lowLink[v]==idx[v]){
    	vector<int> c;
           int s;
		   do{
           	 s= S.top();
           	 S.pop();
           	 c.push_back(s);
           	 inStack[s]=-1;
		   } while(s!=v);  
		 rez.push_back(c);    	
	}	
}



int main(){
	ifstream in("ctc.in");
	int n, m, x, y, i;
	in>>n>>m;
	vector<int> adj[n+1]; 
	
	//intializing vectors
	idx.resize(n+1); inStack.resize(n+1); lowLink.resize(n+1);
	idx.assign(n+1,-1); inStack.assign(n+1,-1);
	
	//data reading
	for(i=1;i<=m;i++){
		in>>x>>y;
		adj[x].push_back(y);
	}
	in.close();
	
	
	//Tarjan
	for(i=1;i<=n;i++)
	   if(idx[i]==-1) 
	       Tarjan(i,adj);
	
	
	//writing solution
	FILE *out=fopen("ctc.out","w");
	fprintf(out,"%i\n",rez.size());
	for(i=0;i<rez.size();i++){
		for(int j=0;j<rez[i].size();j++)
		    fprintf(out,"%lld ",rez[i][j]);
		fprintf(out,"\n");    
	}
	fclose(out);
	return 0;
}