爆零后的感受外加一道强联通分量HDU 4635的题解

view code#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 100010;
int _, cas=1, n, m;
int in[N], out[N], num[N];

vector<int > G[N];
int pre[N], lowlink[N], dfs_clock, scc_cnt, sccno[N];
stack<int >S;

void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    int siz = G[u].size();
    for(int i=0; i<siz; i++)
    {
        int v = G[u][i];
        if(!pre[v])
        {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if(!sccno[v])
        {
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if(lowlink[u] == pre[u])
    {
        scc_cnt++;
        for(;;)
        {
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            num[scc_cnt]++;
            if(x==u) break;
        }
    }
}

void find_scc()
{
    dfs_clock = 0;
    scc_cnt = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    for(int i=1; i<=n; i++)
    {
        if(!pre[i]) dfs(i);
    }
}

void solve()
{
    scanf("%d%d", &n ,&m);
    memset(num, 0, sizeof(num));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    for(int i=1; i<=n ;i++) G[i].clear();

    int u, v;
    for(int i=0; i<m; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    find_scc();
    printf("Case %d: ", cas++);
    if(scc_cnt==1)
    {
        printf("-1\n");
        return ;
    }
    ll ans = 0, Min = INF;
    for(int i=1; i<=n; i++)
    {
        int siz = G[i].size();
        for(int j=0; j<siz; j++)
        {
            if(sccno[i]!=sccno[G[i][j]])
            {
                in[sccno[G[i][j]]]++;
                out[sccno[i]]++;
            }
        }
    }
    for(int i=1; i<=scc_cnt; i++)
    {
        if((in[i]==0 || out[i]==0)  && Min>num[i]) Min = num[i];
//        printf("num[%d] = %d\n", i, num[i]);
//        printf("out = %d, in = %d\n", out[i], in[i]);
    }
    ans  = (Min-1)*Min- m + (n-Min)*(n-Min-1)+Min*(n-Min);
    cout<<ans<<endl;
}

int main()
{
//    freopen("in", "r", stdin);
    cin>>_;
    while(_--) solve();
    return 0;
}

view code#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N = 55555;
const int INF = 1<<30;
int n, pos[N<<2], Max[N<<2];

struct node
{
    char str[55];
    int data;
    bool operator < (const node &o) const{
        return strcmp(str,o.str)<0;
    }
}sto[N];

void Up(int rt)
{
    int ls = rt<<1, rs=ls|1;
    if(Max[rs]>Max[ls]) pos[rt] = pos[rs], Max[rt] = Max[rs];
    else pos[rt] = pos[ls], Max[rt] = Max[ls];
}

void build(int l, int r, int rt)
{
    if(l==r)
    {
        Max[rt] = sto[l].data;
        pos[rt] = l;
        return ;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    Up(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if(L<=l && R>=r) return pos[rt];
    int m = (l+r)>>1;
    if(R<=m) return query(L, R, lson);
    if(L>m) return query(L, R, rson);
    int lpos = query(L, R, lson);
    int rpos = query(L, R, rson);
    return sto[lpos].data<sto[rpos].data?rpos:lpos;
}

void print(int l, int r)
{
    if(l>r) return ;
    if(l==r)
    {
        printf("(%s/%d)", sto[l].str, sto[l].data);
        return ;
    }
    int m = query(l, r, 0, n-1, 1);
    printf("(");
    print(l, m-1);
    printf("%s/%d", sto[m].str, sto[m].data);
    print(m+1,r);
    printf(")");
}

void solve()
{
    for(int i=0; i<n; i++)
    {
        scanf(" %[a-z]/%d", sto[i].str, &sto[i].data);//这个输入方式。。又涨姿势了
//        printf("%s/%d\n", sto[i].str, sto[i].data);
    }
    sort(sto, sto+n);
    build(0, n-1, 1);
    print(0, n-1);
    printf("\n");
}

int main()
{
//    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n)>0 && n) solve();
    return 0;
}