Pagini recente » Cod sursa (job #2162148) | Cod sursa (job #3214488) | Cod sursa (job #859470) | Cod sursa (job #1839203) | Cod sursa (job #2978700)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int N = 100005;
vector<int> graph[N];
int n, m, low[N], idx, id[N], cnt;
vector<vector<int>> components;
stack<int> s;
bool on_stack[N];
void tarjan(int u) {
low[u] = idx;
id[u] = idx++;
s.push(u);
on_stack[u] = true;
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if (id[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (on_stack[v]) {
low[u] = min(low[u], id[v]);
}
}
if (low[u] == id[u]) {
components.push_back(vector<int>());
int v;
do {
v = s.top();
s.pop();
on_stack[v] = false;
components[cnt].push_back(v);
} while (u != v);
cnt++;
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
fin >> u >> v;
graph[u].push_back(v);
}
memset(id, -1, sizeof id);
for (int i = 1; i <= n; i++) {
if (id[i] == -1) tarjan(i);
}
fout << cnt << endl;
}