Pagini recente » Cod sursa (job #1701448) | Cod sursa (job #72201) | Cod sursa (job #2102683) | Cod sursa (job #2351129) | Cod sursa (job #1038368)
/*#include<fstream>
#define NMAX 10000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
/*
//varianta 1
int D[NMAX][NMAX],n,viz[NMAX],m,x,y;
void citire()
{
int i,j;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
D[x][y]=1;
}
}
void construire()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(D[i][k] && D[k][j])
D[i][j]=1;
}
void rezolvare(int x)
{
int i,j;
for(j=1;j<=n;j++)
{
if(viz[j]==0)
{
viz[j]=1;
fout<<j<<" ";
for(i=1;i<=n;i++)
{
if(D[j][i]==1 && D[i][j]==1 && viz[i]==0)
{
viz[i]=1;
fout<<i<<" ";
}
}
fout<<"\n";
}
}
}
int main()
{
citire();
construire();
rezolvare(1);
}*/
//varianta 3
/*
int n,m,i,nrp;
int G[NMAX][NMAX],GT[NMAX][NMAX];
int postordine[NMAX],viz[NMAX];
void citire()
{
int x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
G[x][y]=1;
GT[y][x]=1;
}
}
void DFS(int x)
{
int St[NMAX],k,v,y;
St[1]=x;
viz[x]=1;
k=1;
while(k)
{
v=St[k];
y=0;
for(i=1;i<=n;i++)
{
if(G[v][i] && viz[i]==0)
{
y=i;
break;
}
}
if(y==0) k--;
else
{
viz[y]=1;
St[++k]=y;
}
}
postordine[++nrp]=i;
}
void DFST(int x)
{
int St[NMAX],k,v,y;
St[1]=x;
viz[x]=1;
fout<<x<<" ";
k=1;
while(k)
{
v=St[k];
y=0;
for(i=1;i<=n;i++)
{
if(GT[v][i] && viz[i]==0)
{
y=i;
break;
}
}
if(y==0) k--;
else
{
viz[y]=1;
fout<<y<<" ";
St[++k]=y;
}
}
}
int main()
{
citire();
for(i=1;i<=n;i++)
{
if(viz[i]==0)
DFS(i);
}
for(i=1;i<=n;i++) viz[i]=0;
for(i=nrp;i>=1;i--)
{
if(viz[postordine[i]]==0)
DFST(postordine[i]);
fout<<"\n";
}
return 0;
}*/
#include <fstream>
#include<cstdio>
#include <vector>
#define NMAX 100002
using namespace std;
FILE *fin,*fout;
int n,m,nr,ctc;
vector <int> G[NMAX];
vector <int> Gt[NMAX];
vector <int> M[NMAX];
int use[NMAX];
int postordine[NMAX];
void cit()
{
int i,x,y;
fin=fopen("ctc.in","r");
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&x,&y);
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void dfs(int vf)
{
int i,nra;
nra=G[vf].size();
use[vf]=1;
for(i=0;i<nra;i++)
{
if(!use[G[vf][i]])
{
dfs(G[vf][i]);
}
}
postordine[++nr]=vf;
}
void dfst(int vf)
{
int i,nra;
nra=Gt[vf].size();
use[vf]=0;
M[ctc].push_back(vf);
for(i=0;i<nra;i++)
{
if(use[Gt[vf][i]])
dfst(Gt[vf][i]);
}
}
int main()
{
int i;
cit();
nr=0;
for(i=1;i<=n;i++)
{
if(!use[i])
dfs(i);
}
for(i=n;i>=1;i--)
{
if(use[postordine[i]])
{
dfst(postordine[i]);
ctc++;
}
}
fprintf(fout,"%d",ctc);
return 0;
}