Pagini recente » Cod sursa (job #13409) | Cod sursa (job #2987607) | Cod sursa (job #3282) | Cod sursa (job #3223697) | Cod sursa (job #2538809)
#define DM 100001
#define inf 0x3f3f3f3f
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fi ("echipe.in");
ofstream fo ("echipe.out");
bool ins[DM];
int n, m, a, b, idx[DM], ctc[DM], total, midx[DM], nw;
stack <int> st;
vector <int> v[DM];
void discover(int nod) {
idx[nod] = midx[nod] = ++nw;
ins[nod] = 1;
st.push(nod);
for (auto i:v[nod]) {
if (idx[i] < idx[nod] && ins[i]) {
midx[nod] = min(idx[i], midx[nod]);
} else if (idx[i] == inf) {
discover(i);
midx[nod] = min(midx[i], midx[nod]);
}
}
if (midx[nod] == idx[nod]) {
++total;
while (st.top() != nod) {
ctc[st.top()] = total;
st.pop();
}
ctc[nod] = total;
st.pop();
}
ins[nod] = 0;
}
int main() {
fi >> n >> m;
for (int i = 1; i <= n; ++i)
idx[i] = inf;
for (int i = 1; i <= m; ++i) {
fi >> a >> b;
v[a].push_back(b);
}
for (int i = 1; i <= n; ++i)
if (!ctc[i])
discover(i);
fo << total;
return 0;
}