Pagini recente » Cod sursa (job #1668161) | Cod sursa (job #2067761) | Cod sursa (job #62953) | Cod sursa (job #534245) | Cod sursa (job #1890116)
#include<bits/stdc++.h>
#define N 100020
using namespace std;
vector <int> lda[N], lda1[N];
int t, v[N], c[N], col=0, b=0;
struct nod{
int val;
nod* next;
nod(){
next=NULL;
}
};
nod* L=NULL;
struct p{
int v, ind;
} a[N];
ifstream f("ctc.in");
ofstream g("ctc.out");
void add(nod* &a, int val){
if(a==NULL){
a = new nod;
a->val=val;
return;
}
nod* b=new nod;
b->val=val;
b->next=a;
a=b;
}
void dfs(int nod){
v[nod]=1;
int i;
for(i=0;i<lda[nod].size();i++)if(!v[lda[nod][i]]){
dfs(lda[nod][i]);
}
++t;
a[nod].v=t;
a[nod].ind=nod;
}
void dfs1(int nod){
v[nod]=1;
add(L, nod);
int i;
for(i=0;i<lda1[nod].size();i++)if(!v[lda1[nod][i]]){
dfs1(lda1[nod][i]);
}
c[nod]=col;
}
int cmp(p a, p b){
return(a.v>b.v);
}
int main(){
int i, n, m, j, x, y;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
lda[x].push_back(y);
lda1[y].push_back(x);
}
for(i=1;i<=n;i++)if(!v[i]){
// col++;
dfs1(i);
}
for(i=1;i<=n;i++)v[i]=0;
nod* r=L;
for(; r;r=r->next){
if(!v[r->val]){
col++;
dfs(r->val);
}
}
g<<col;
return 0;
}