Pagini recente » Cod sursa (job #3207130) | Cod sursa (job #2821189) | Cod sursa (job #1746) | Cod sursa (job #752856) | Cod sursa (job #243608)
Cod sursa(job #243608)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 50900
vector<int> g[MAXN],gt[MAXN];
//g - graful dat, gt - graful transpus grafului g
int n, m;
//n - nr noduri; m - nr muchii
int nrctc;
//nrctc - nr de componente tare conexe
int fol[MAXN];
bool pls[MAXN],mins[MAXN];
//fol[i]-un nr natural <=n
//daca fol[i]==0 nodul i nu a fost folosit inca intr-o comp t conexa
// daca fol[i]!=0 atunci nodul i a fost folosit in comp t conexa fol[i];
void df1(int nod){
pls[nod]=1;
vector<int>::iterator it;
for(it=g[nod].begin();it!=g[nod].end();++it)
if(!pls[*it]&&!fol[*it])
df1(*it);
}
void df2(int nod){
mins[nod]=1;
vector<int>::iterator it;
for(it=gt[nod].begin();it!=gt[nod].end();++it)
if(!mins[*it]&&!fol[*it])
df2(*it);
}
int main(){
int i, x, y, j;
//citire date
ifstream f("ctc.in");
f>>n>>m;
for(i=0;i<m;i++){
f>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
f.close();
for(i=1; i<=n; i++){
if(!fol[i]){
df1(i);
df2(i);
nrctc++;
for(j=1;j<=n;j++)
if(pls[j]&&mins[j])
fol[j]=nrctc;
memset(pls,0,sizeof(pls));
memset(mins,0,sizeof(mins));
}
}
ofstream g("ctc.out");
g<<nrctc<<'\n';
for(i=1;i<=nrctc;i++){
for(j=1;j<=n;j++)
if(fol[j]==i)
g<<j<<' ';
g<<'\n';
}
g.close();
return 0;
}