Pagini recente » Cod sursa (job #2040525) | Cod sursa (job #494008) | Cod sursa (job #2279360) | Cod sursa (job #943352) | Cod sursa (job #2542940)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<bitset>
using namespace std;
int n,id=0,ids[100010],low[100010],ctc=0;
vector <int> v[100010],cc[100010];
stack <int> S;
bitset <100010> onStack;
void citire(){
ifstream f("ctc.in");
int m,i,x,y; f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
v[x].push_back(y);
}
f.close();
}
void dfs(int k){
ids[k]=low[k]=++id; int i;
S.push(k); onStack[k]=1;
for(i=0;i<v[k].size();i++){
if(!ids[v[k][i]]){
dfs(v[k][i]);
low[k]=min(low[k],low[v[k][i]]);
}
else if(onStack[v[k][i]]) low[k]=min(low[k],low[v[k][i]]);
}
if(ids[k]==low[k]){
ctc++; int x;
while(1){
x=S.top();
S.pop();
cc[ctc].push_back(x);
onStack[x]=0;
if(k==x) break;
}
}
}
void tarjan(){
int i;
for(i=1;i<=n;i++)
if(!ids[i]) dfs(i);
}
void afisare(){
ofstream o("ctc.out");
o<<ctc<<endl; int i,j;
for(i=1;i<=ctc;i++){
for(j=0;j<cc[i].size();j++)
o<<cc[i][j]<<" ";
o<<endl;
}
o.close();
}
int main(){
citire();
tarjan();
afisare();
}