练习

//走迷宫 
#include<bits/stdc++.h>
using namespace std;
int front,rear,r,c,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},q[10010][3],lx,ly,mx,my;
char a[110][110];
void bfs();
int main()
{
    cin>>r>>c;
    if(r==0&&c==0)
        return 0;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='S')
                lx=i,ly=j;
            if(a[i][j]=='T')
                mx=i,my=j;
        }
    front=0,rear=1;
    q[rear][0]=lx,q[rear][1]=ly,q[rear][2]=0;
    a[lx][ly]=1;
    bfs();
    cout<<q[rear][2];
    return 0;
}
void bfs()
{
    while(front<rear)
    {
        front++;
        for(int i=0;i<4;i++)
        {
            int xx=q[front][0]+dx[i];
            int yy=q[front][1]+dy[i];
            if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&a[xx][yy]!='#')
            {
                rear++;
                q[rear][0]=xx;
                q[rear][1]=yy;
                q[rear][2]=q[front][2]+1;
                a[xx][yy]='#';
                if(xx==mx&&yy==my)
                    return;
            }
        }
    }
}

//资料发放 
#include<bits/stdc++.h>
using namespace std;
vector<int> g[201];
queue<int> f;
int visw[201]={0},s=0;
void bfs(int y){
    f.push(y);
    visw[y]=1;
    while(!f.empty()){
        int h=f.front();
        f.pop();
        for(int i=0; i<g[h].size(); i++){
            int l=g[h][i];
            if(visw[l]==0){
                f.push(l);
                visw[l]=1;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; ; j++){
        int a;
        cin>>a;
        if(a==0) break;
        else g[i].push_back(a);
        }
    }
    for(int i=1; i<=n; i++){
        if(visw[i]==0){
            s++;
            bfs(i);
        } 
    }
    cout<<s<<endl;
    return 0;
}

//关系网络 
#include<bits/stdc++.h>
using namespace std;
int a[101][101],f[101],t[101]; 
int n,x,y;  
queue<int>bh; 
int bfs(int x) 
{   
    bh.push(x);  
    t[x]=0; f[x]=1; 
    while(bh.empty()!=1)  
    {   
        int i=bh.front();  
        if(i==y){ return t[i]-1;}  
        for(int j=1;j<=n;j++) 
        {   
            if(a[i][j]==1&&f[j]==0)  
            {  
                bh.push(j);     
                t[j]=t[i]+1;     
                f[j]=1;        
            }
        }
        bh.pop();   
    }
}
int main()
{   
    int i,j;  
    cin>>n>>x>>y;
    for(i=1;i<=n;i++)
    {   
        for(j=1;j<=n;j++)
        {   
            cin>>a[i][j];
      }
    }
    cout<<bfs(x);  
}

//targan算法 
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,cntb;
vector<int> edge[101];
int siz[101];
bool instack[101];
int dfn[101];
int low[101];
stack<int> s;
void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    s.push(u);
    instack[u]=true;
    for(int i=0; i<edge[u].size(); i++){
        int v=edge[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++cntb;
        int node;
        while(node!=u){
            node=s.top();
            s.pop();
            instack[node]=false;
            siz[cntb]++;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            tarjan(i);
    int ans=0;
    for(int i=1; i<=cntb; i++){
        ans=max(ans,siz[i]);
    }
    cout<<ans<<endl;         
    return 0;
}

//亲戚 
#include<bits/stdc++.h>
using namespace std;
int fu[500001];
int find(int n){
    if(fu[n]==n) return n;
    else{
        fu[n]=find(fu[n]);
        return fu[n];
    }
}
void merge(int n,int m){
    fu[find(n)]=find(m);
}
int main(){
    int n,m,p,x,y;
    cin>>n>>m>>p;
    for(int i=1; i<=10000; i++) fu[i]=i;
    for(int i=1; i<=m; i++){
        cin>>x>>y;
        merge(x,y);
    }
    for(int i=1; i<=p; i++){
        cin>>x>>y;
        if(find(x)==find(y)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}