头像

酸奶瓜皮




离线:1天前


最近来访(7)
用户头像
Charl3s
用户头像
AlbertBigcomeLu
用户头像
Finn2009
用户头像
夏鹏今天学习了嘛
用户头像
卿故倾.
用户头像
kaikaihapppy


N=100010
n,m=0,0
d=[0]*N
q=[0]*N
h=[-1]*N
e=[0]*N
ne=[0]*N
idex=0
def add(a,b):
    global n,m,q,h,e,ne,idex
    e[idex]=b
    ne[idex]=h[a]
    h[a]=idex
    idex+=1
def bfs():
    global n,m,q,h,e,ne,idex
    hh,tt=0,-1
    for i in range(1,n+1):
        if d[i]==0:
            tt+=1
            q[tt]=i
    while hh<=tt:
        t=q[hh]
        hh+=1
        i=h[t]
        while i!=-1:
            j=e[i]
            d[j]-=1
            if d[j]==0:
                tt+=1
                q[tt]=j
            i=ne[i]
    return tt==n-1        
def main():
    global n,m,q,h,e,ne,idex
    n,m=map(int,input().split())
    for i in range(m):
        a,b=map(int,input().split())
        add(a,b)
        d[b]+=1
    if bfs():
        for i in range(n):
            print(q[i],end=" ")
    else: print("-1")
main()


活动打卡代码 AcWing 847. 图中点的层次

#pragma GCC optimize(2)
#include<iostream>
#include<stdio.h>
#include <cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<math.h>
#include<deque>
#include<string>
#include<unordered_set>
using namespace::std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idex = 0;
int d[N];
int n,m;
int q[N];
int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof(d));
    d[1] = 0;
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++tt] = j;
            }

        }
    }
    return d[n];
}
void add(int a, int b)
{
    e[idex] = b;
    ne[idex] = h[a];
    h[a] = idex++;
}
int main()
{

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout<<bfs();
}


活动打卡代码 AcWing 846. 树的重心

N=100010
M=N*2
h=[-1]*N
ne=[0]*M
e=[0]*M
idex=0
ans=N
st=[False]*N
n=0
def dfs(u):
    global h,ne,idex,ans,st,n
    sum,res=1,0
    st[u]=True
    i=h[u]
    while i!=-1:
        j=e[i]
        if st[j]!=True:
            s=dfs(j)
            res=max(res,s)
            sum+=s
        i=ne[i]
    res=max(res,n-sum)
    ans=min(ans,res)
    return sum
def add(a,b):
    global h,ne,idex,ans,st,n
    e[idex]=b
    ne[idex]=h[a]
    h[a]=idex
    idex+=1
def main():
    global h,ne,idex,ans,st,n
    n=int(input())
    for i in range(n-1):
        a,b = map(int, input().split())
        add(a,b),add(b,a)
    dfs(1)
    print(ans)
main()


活动打卡代码 AcWing 842. 排列数字

n=0
path=[[0]*7]*7
st=[0]*8
def dfs(x):
    global n
    if x==n:
        for i in range(n):
            print(path[i],end=" ")
        print()
    for i in range(1,4):
        if st[i]==0:
            st[i]=1
            path[x]=i
            dfs(x+1)
            st[i]=0
def main():
    global n
    n=int(input())
    dfs(0)
main()


活动打卡代码 AcWing 844. 走迷宫

arr=[]
q=[]
L=[-1,0,1,0]
R=[0,1,0,-1]
n,m=0,0
Distance=[[-1]*100 for i in range(100)]
def bfs():
    global arr,q,L,Distance,R,n,m
    Distance[0][0]=0
    hh,tt=0,0
    q.append((0,0))
    while hh<=tt:
            x,y=q[hh][0],q[hh][1]
            hh+=1
            for i in range(4):
                tx,ty=x+L[i],y+R[i]
                if tx>=0 and tx<n and ty>=0 and ty<m and arr[tx][ty]!=1and Distance[tx][ty]==-1:
                    Distance[tx][ty]=Distance[x][y]+1
                    q.append((tx,ty))
                    tt+=1
                if tx>=0 and tx<n and ty>=0 and ty<m and tx==n-1 and ty==m-1:
                    return Distance[tx][ty];
                    break
def main():
    global arr,q,L,Distance,R,n,m
    n,m=map(int,input().split())
    for i in range(n):
        arr.append(list(map(int, input().split())))
    print(bfs())
main()


活动打卡代码 AcWing 240. 食物链

c++

#pragma GCC optimize(2)
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<math.h>
#include<deque>
#include<string>
#include<unordered_set>
using namespace::std;
int n, m;
const int K = 1e5 + 10;
int d[K];
int p[K];
//本题采用距离法确定关系,x,y距离为0为同类,x,y距离为1为x吃y
int find(int x)
{
    if(p[x]!=x) 
    {
        int t=find(p[x]);//先记录跟结点位置
        d[x]+=d[p[x]];//加上之间的距离
        p[x]=t;//最后赋值根节点
    }
    return p[x];
}
int main()
{
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        int t,x,y;
        cin>>t>>x>>y;
        int wx=find(x),wy=find(y);
        if (x>n||y>n) 
        {
            sum++;
            continue;
        }
        if(t==1)
        {
            if(wx==wy&&(d[x]-d[y])%3) sum++;//x和y的距离是相等的才是同类 d[x]-d[y]=0 不等于0就是错误话
            if(wx!=wy)
            {
                p[wx]=wy;//将wx的祖宗变成wy
                d[wx]=d[y]-d[x];//d[x]+d[wx]=d[y]才是同类
            }
        }
        else
        {
            if(wx==wy&&(d[x]-d[y]-1)%3)sum++; //x和y的距离是相差1才是x吃y d[x]-d[y]=1 不等于1就是错误话
            if(wx!=wy)
            {
                p[wx]=wy;
                d[wx]=d[y]-d[x]+1;//d[x]+d[wx]-d[y]=1才是x吃y
            }
        }
    }
    cout<<sum;
}

python

K=100010
p=[0]*K
d=[0]*K
def find(x):
    global p,d
    if p[x]!=x:
        t=find(p[x])
        d[x]+=d[p[x]]
        p[x]=t
    return p[x]
def main():
    global p,d
    sum=0
    n,m=map(int,input().split())
    for i in range(1,n+1):
        p[i]=i
    while m:
        m-=1
        t, x, y = list(map(int, input().split()))
        if x>n or y>n:
            sum+=1
            continue
        wx,wy=find(x),find(y)
        if t==1:
            if wx==wy and (d[x]-d[y])%3!=0:
                sum+=1
            if wx!=wy:
                p[wx]=wy
                d[wx]=d[y]-d[x]
        else:
            if wx==wy and (d[x]-d[y]-1)%3!=0:
                sum+=1
            if wx!=wy:
                p[wx]=wy
                d[wx]=d[y]-d[x]+1
    print(sum)
main()


活动打卡代码 AcWing 840. 模拟散列表

N=200010
null=0x3f3f3f3f
arr=[null]*N
def find(x):
    global arr,N
    k=(x%N+N)%N
    while arr[k]!=null and arr[k]!=x:
        k+=1
        if k==N:
            k=0
    return k
def main():
    global arr
    n=int(input())
    for i in range(n):
        p,x=input().split()
        x=int(x)
        k=find(x)
        if p=='I':
            arr[k]=x
        else:
            if arr[k]==x:
                print("Yes")
            else:
                print("No")
main()



p=[0 for i in range(100010)]
shu=[0 for i in range(100010)]
def find(x):
    global p,shu
    if p[x]!=x:
        p[x]=find(p[x])
    return p[x]
def main():
    global o,shu
    n,m=map(int,input().split())
    for i in range(1,n+1):
        p[i]=i
        shu[i]=1
    for i in range(m):
        P=input().split()
        if P[0]=="C":
            a,b=int(P[1]),int(P[2])
            if find(a)==find(b):
                continue
            shu[find(b)]+=shu[find(a)]
            p[find(a)]=find(b)
        elif P[0]=="Q1":
            a,b=int(P[1]),int(P[2])
            if find(a)==find(b):
                print("Yes")
            else:
                print("No")
        else:
            a=int(P[1])
            print(shu[find(a)])
main()


活动打卡代码 AcWing 836. 合并集合

p=[0 for i in range(100010)]
def find(x):
    global p
    if p[x]!=x:
        p[x]=find(p[x])
    return p[x]
def main():
    global p
    n,m=map(int,input().split())
    for i in range(1,n+1):
        p[i]=i
    for i in range(m):
        P,a,b=input().split()
        a,b=int(a),int(b)
        if P=='M':
            p[find(a)]=find(b)
        else:
            if find(a)==find(b):
                print("Yes")
            else:
                print("No")
main()


活动打卡代码 AcWing 835. Trie字符串统计

arr = [[0] * 26 for i in range(100010)]
cnt=[0]*100010
idex=0
def insert(s):
    global cnt,idex,arr
    p=0
    for i in range(len(s)):
        a=ord(s[i])-ord('a')#转换为ASCII用ord,不能像c直接用s[i]-'a'
        if arr[p][a]==0:
            idex+=1
            arr[p][a]=idex
        p=arr[p][a]
    cnt[p]+=1
def inqury(s):
    global cnt,idex,arr
    p=0
    for i in range(len(s)):
        a=ord(s[i])-ord('a')
        if arr[p][a]==0:
            print(0)
            return;
        p=arr[p][a]
    print(cnt[p])        
def main():
    global cnt,idex,arr
    n=int(input())
    for i in range(n):
        p,s=input().split()
        s=list(s)
        if p=='I':
            insert(s)
        else:
            inqury(s)
main()