NKONEARC - Mạng máy tính

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int num[2020],low[2020],lab[2020],pos[2020],cnt = 0,com = 0;
int n,m,x[30010],y[30010];
stack<int> s;
map< pair<int,int>,bool > mp;
bool in[2020],ou[2020],used[2020];
vector<int> adj[2020];

void DFS(int u)
{
     num[u] = low[u] = ++cnt;  s.push(u);
     for (int i = 0; i < adj[u].size(); i++)
     {
         int v = adj[u][i];
         if (!used[v]) continue;
         if (!num[v])
         {
            DFS(v);  low[u] = min(low[u],low[v]);
         }
         else low[u] = min(low[u],num[v]);
     }
     
     if (num[u] == low[u])
     {
       com++;
       while (1)
       {
         lab[com] = s.top(); s.pop();  pos[lab[com]] = com;  used[lab[com]] = false;  if (lab[com] == u) break;
       }
     }
 }

int main()
{
//    freopen("nkonearc.in","r",stdin);
//    freopen("nkonearc.ou","w",stdout);   
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {   
        scanf("%d %d", &x[i], &y[i]);    
        if (x[i] == y[i] || mp[make_pair(x[i],y[i])]) continue;
        mp[make_pair(x[i],y[i])] = true;
        adj[x[i]].push_back(y[i]);
    }
    memset(used,true,sizeof(used));
    memset(in,true,sizeof(in));
    memset(ou,true,sizeof(ou));
    for (int i = 1; i <= n; i++) if (used[i]) DFS(i);
    for (int i = 0; i < m; i++) if (pos[x[i]] != pos[y[i]])
    {
        ou[pos[x[i]]] = false;  in[pos[y[i]]] = false;
    }
    int fin = 1,fou = 1;
    for (int i = 1; i <= com; i++)
    {
        if (in[i]) fin = lab[i];  if (ou[i]) fou = lab[i];
    }
    printf("YES\n");
    printf("%d %d\n", fou, fin);
}

Download