Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- using namespace std;
- const int maxgr = 1e4 + 1;
- vector<int> gr[maxgr], antigr[maxgr], gr_component[maxgr], antigr_component[maxgr];
- set< pair<int, int> > vecsort, vecsort_component, rebra_component;
- int topsort[maxgr], topsort_component[maxgr], colorgr[maxgr];
- bool used[maxgr];
- void dfs_topsort(int& timer, int v) { // топологическая сортировка обычного графа
- used[v] = true;
- for (int i = 0; i < antigr[v].size(); ++i) {
- int to = antigr[v][i];
- if (!used[to]) {
- dfs_topsort(timer, to);
- }
- }
- topsort[v] = timer++;
- vecsort.insert(make_pair(-topsort[v], v)); // добавление элементов в упорядоченности по убыванию по топсорт
- }
- void dfs_component_topsort(int& timer, int v) { // топологическая сортировка графа компонент сильной связаности
- used[v] = true;
- for (int i = 0; i < antigr_component[v].size(); ++i) {
- int to = antigr_component[v][i];
- if (!used[to]) {
- dfs_component_topsort(timer, to);
- }
- }
- topsort_component[v] = timer++;
- vecsort_component.insert(make_pair(-topsort_component[v], v));
- }
- void dfs_component_rebra(int v, int color) {
- colorgr[v] = color;
- vecsort.erase(make_pair(-topsort[v], v)); // удаление элемента компоненты
- for (int i = 0; i < gr[v].size(); ++i) {
- int to = gr[v][i];
- if (!colorgr[to]) {
- dfs_component_rebra(to, color);
- }
- else if (colorgr[to] != color) {
- rebra_component.insert(make_pair(colorgr[v], colorgr[to]));
- }
- }
- }
- void dfs_cradle_search(int v) {
- used[v] = true;
- vecsort_component.erase(make_pair(-topsort_component[v], v));
- for (int i = 0; i < antigr_component[v].size(); ++i) {
- int to = antigr_component[v][i];
- if (!used[to]) {
- dfs_cradle_search(to);
- }
- }
- }
- int main() {
- int n, m;
- cin >> n >> m;
- int cur1, cur2;
- for (int i = 0; i < m; ++i) {
- cin >> cur1 >> cur2;
- cur1--;
- cur2--;
- gr[cur1].push_back(cur2);
- antigr[cur2].push_back(cur1);
- }
- int timer = 0;
- for (int i = 0; i < n; ++i) {
- if (!used[i]) {
- dfs_topsort(timer, i); // топологическая сортировка
- }
- }
- memset(used, 0, sizeof(used));
- vector<int> col_ver(1, -1);
- int color = 1;
- while (vecsort.size() > 0) {
- col_ver.push_back(vecsort.begin()->second); // добавление вершины за основу компоненты
- dfs_component_rebra(vecsort.begin()->second, color);
- color++;
- }
- memset(used, 0, sizeof(used));
- for (auto curr : rebra_component) {
- gr_component[curr.first].push_back(curr.second);
- antigr_component[curr.second].push_back(curr.first);
- }
- timer = 0;
- for (int i = 1; i < color; ++i) {
- if (!used[i]) {
- dfs_component_topsort(timer, i);
- }
- }
- memset(used, 0, sizeof(used));
- set<int> cradle; // количество истоков
- while (vecsort_component.size() > 0) {
- cradle.insert(col_ver[vecsort_component.begin()->second]);
- dfs_cradle_search(vecsort_component.begin()->second);
- }
- cout << cradle.size() << endl;
- for (auto curr : cradle) {
- cout << curr + 1 << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement