Submission #811025

#	Time	Username	Problem	Language	Result	Execution time	Memory
811025		JakobZorz	Pipes (CEOI15_pipes)	C++14	0 / 100	1247 ms	65536 KiB

pipes

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second
 
int n,m;
vector<int> nodes[100000];
vector<int> dir[100000];
vector<int> dir2[100000];
int depths[100000];
vector<int>nodes_order;
bool vis1[100000];
int cc[100000];

void dfs1(int node,int depth,int par){
    if(depths[node])
        return;
    depths[node]=depth;
    for(int ne:nodes[node]){
        if(depths[ne]<depths[node]&&ne!=par){
            dir[node].push_back(ne);
            dir2[ne].push_back(node);
            //cout<<node+1<<" -> "<<ne+1<<"\n";
            dfs1(ne,depth+1,node);
        }
    }
}

void dfs2(int node){
    if(vis1[node])
        return;
    vis1[node]=true;
    nodes_order.push_back(node);
    for(int ne:dir2[node])
        dfs2(ne);
}

void dfs3(int node,int curr_cc){
    if(cc[node])
        return;
    cc[node]=curr_cc;
    for(int ne:dir[node])
        dfs3(ne,curr_cc);
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        nodes[a].push_back(b);
        nodes[b].push_back(a);
    }
    
    for(int i=0;i<n;i++)
        dfs1(i,1,i);
    for(int i=0;i<n;i++)
        dfs2(i);
    reverse(nodes_order.begin(),nodes_order.end());
    
    int curr_cc=1;
    for(int node:nodes_order)
        if(cc[node]==0)
            dfs3(node,curr_cc++);
    
    /*for(int node:nodes_order)
        cout<<node+1<<" ";
    cout<<"\n";
    
    for(int i=0;i<n;i++)
        cout<<cc[i]<<" ";
    cout<<"\n";*/
    
    for(int i=0;i<n;i++)
        for(int j:dir[i])
            if(cc[i]!=cc[j])
                cout<<i+1<<" "<<j+1<<"\n";
    
    return 0;
}

/*
 
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
 
 */

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10