Pagini recente » Cod sursa (job #2733059) | Cod sursa (job #3183404) | Cod sursa (job #3225332) | Cod sursa (job #1215159) | Cod sursa (job #2328171)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX= 100003;
vector <int> gr[MAX], comp[MAX];
stack <int> s, afis;
bool viz[MAX];
int n, m, id[MAX], low[MAX], nc, urm;
//ifstream in("ctc.in");
//ofstream out("ctc.out");
void tarjan(int nod){
id[nod] = low[nod] = ++urm;
s.push(nod);
viz[nod] = true;
for(unsigned i=0; i<gr[nod].size(); i++)
if(id[gr[nod][i]]==0){
tarjan(gr[nod][i]);
low[nod] = min(low[nod], low[gr[nod][i]]);
}
else
if(viz[gr[nod][i]]==true)
low[nod] = min(low[nod], low[gr[nod][i]]);
if(id[nod] == low[nod]){
nc++;
int v;
do{
v = s.top();
s.pop(); viz[v] = false;
afis.push(v);
}while(v!=nod);
}
}
int main()
{
int i, u, v;
cin>>n>>m;
for(i=1; i<=m; i++){
cin>>u>>v;
gr[u].push_back(v);
}
for(i=1; i<=n; i++)
if(id[i]==0)
tarjan(i);
cout<<nc;
/* while(!afis.empty()){
int v = afis.top();
afis.pop();
if(id[v] == low[v]) fout<<'\n';
fout<<v<<' ';
}
*/
return 0;
}