Pagini recente » Cod sursa (job #1337693) | Cod sursa (job #1937693) | Monitorul de evaluare | Borderou de evaluare (job #639305) | Cod sursa (job #3313744)
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,i,j,x,y,comp;
bool f[N];
stack<int> s;
vector<int> e[N],r[N];
void dfs1(int x)
{
f[x]=1;
for(auto y:e[x])
{
if(!f[y])
{
f[y]=1;
dfs1(y);
}
}
s.push(x);
}
int dfs2(int x)
{
int s=1;
f[x]=1;
for(auto y:r[x])
{
if(!f[y])
{
f[y]=1;
s+=dfs2(y);
}
}
return s;
}
void kosaraju()
{
int i,j;
for(i=1;i<=n;++i)
{
if(!f[i]) dfs1(i);
}
for(i=1;i<=n;++i)
{
f[i]=0;
}
while(!s.empty())
{
int x=s.top();
s.pop();
if(!f[x])
{
if(dfs2(x)==1) ++comp;
//cout<<dfs2(x)<<'\n';
}
}
}
int main()
{
cin>>n>>m;
while(m--)
{
cin>>x>>y;
e[x].push_back(y);
r[y].push_back(x);
}
kosaraju();
cout<<comp;
return 0;
}