Pagini recente » Cod sursa (job #66734) | Cod sursa (job #20714) | Cod sursa (job #1273487) | Cod sursa (job #2796687) | Cod sursa (job #2251856)
//Tarjan
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
vector <int> idx, lowLink, inStack;
vector <vector<int> > rez;
stack<int> S;
void Tarjan(int v, vector<int> *adj, int indecs){
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,indecs);
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,0);
//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,"%i ",rez[i][j]);
fprintf(out,"\n");
}
fclose(out);
return 0;
}