Pagini recente » Cod sursa (job #2819337) | Cod sursa (job #1747685) | Cod sursa (job #1904026) | Cod sursa (job #845534) | Cod sursa (job #1068755)
#include <fstream>
#include <algorithm>
#include<vector>
using namespace std;
int componente,i,aux,n,k,j,p,s,unu,t,m,doi,x,q,st,dr,maxi,sol,maxi2,viz[100010],y,conex,postordine[100100];
vector <int> v[100010],w[100010];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void clean()
{
int j;
for(j=1;j<=n;j++) viz[j]=0;
}
void dfs(int x) {
int i, y;
viz[x] = 1;
//printf("%d ",x);
for (i = 0; i < v[x].size(); i++) {
y = v[x][i];
if (viz[y]==0)
dfs(y);
}
k++;
postordine[k]=x;
}
void dfs2(int x) {
int i, y;
viz[x] = 1;
//fout<<x<<" ";
for (i = 0; i < w[x].size(); i++) {
y = w[x][i];
if (viz[y]==0)
dfs2(y);
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
v[x].push_back(y);
w[y].push_back(x);
}
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
dfs(i);
}
}
clean();
for(i=k;i>=1;i--)
{
if(viz[postordine[i]] ==0)
{
//fout<<postordine[i];
dfs2(postordine[i]);
// fout<<"\n";
componente++;
}
}
fout<<componente<<"\n";
for(i=k;i>=1;i--)
{
// fout<<postordine[i]<<" ";
}
}