Untitled

mail@pastecode.io avatar
unknown
plain_text
12 days ago
2.0 kB
10
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
// ------------------------MeMe-----------------------//

const long long mod = 1e9 + 7;
const int N = 1e3 + 17;

set< int >adj[N] ;
int n , m ;


void code() {
    cin >> n >> m ;

    for( int i = 0 ; i < m ; i++ ){
        int x , y ;
        cin >> x >> y ;
        x-- , y-- ;
        adj[x].insert(y) ;
    }


    
    set< int > now ;
    vector< int > vis(n , 0) ;

    function<void(int , int, int)> dfs =[&]( int u , int p , int node ){
        now.insert(u) ;
        vis[u] = 1 ;
        for( auto v : adj[u] ){
            if( vis[v] )
                continue;
            
            dfs( v , u , node ) ;
        }
    };
   
    vector< pair< int , int > > ans ;
   
    for( int i = 0 ; i < n ; i++ ){
        now.clear() ;
        for( int j = 0 ; j < n ; j++ )
            vis[j] = 0 ;

        dfs( i , i , i ) ;

        for( auto u :  now){
            if( adj[i].find(u) != adj[i].end() )
                continue;
            ans.push_back({ i , u }) ;
        }
    }

    cout << ans.size()  << "\n" ;
    for( auto u : ans )
        cout << u.first + 1 << " " << u.second + 1 << "\n";

}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("err.txt", "w", stderr);
    #endif
    //pre();
    int tt = 1;
    // cin >> tt;
    for (int tn = 1 ; tn <= tt ; tn++) {
        #ifndef ONLINE_JUDGE
        cout << "_________Test_" << tn << "_________" << endl;
        cerr << "_________Test_" << tn << "_________" << endl;
        #endif
        code();
    }

    #ifndef ONLINE_JUDGE
    cout << "________________________" ;
    cerr << "________________________" ;
    #endif
    return 0;
}
Leave a Comment