[Acwing] 367. 学校网络 tarjan的基本使用

前言

传送门 :

思路

题目很明显的让我们 t a r j a n tarjan tarjan了

问题1 . 最少需要多少个学校 问题2 . 至少需要连多少边

问题1. 显然,我们只需要将 t a r j a n tarjan tarjan之后的图,计算一边入度和出度

我们只需要统计有多个入度=0的点即可

问题2. 显然我们可以在 入度 = 0 和 出度 =0 的点里面 取一个 m i n n minn minn即可

CODE

// Problem: 学校网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/369/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
const int N = 110;

map mp;
stack stk;
int cnt,scc[N];
int dfn[N],low[N],idx;
bool inst[N];
int in[N],out[N];
vector g[N];
int n;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk.push(u); inst[u] = 1;

    for (int v : g[u]) {
        if (dfn[v] == 0) {
            tarjan(v);
           	low[u] = min(low[u],low[v]);
        }
        else if (inst[v]) low[u] = min(low[u],dfn[v]);
    }

    if (low[u] == dfn[u]) {
        ++cnt;
        int v;
        do {
            v = stk.top(); stk.pop(); inst[v] = 0;
            scc[v] = cnt;
        } while (v != u);
    }
}
void solve(){
	cin>>n;
	for(int i=1;i>x,x){
			g[i].pb(x);
		}
	}
	
	for(int i=1;i