Cod sursa(job #3282523)

Utilizator WiseAndrei4Vetrila Andrei WiseAndrei4 Data 5 martie 2025 20:41:13
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <vector>
#include <set>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
bool *viz;
vector<int>s;
vector<int>g[101],gt[101];
void dfs(int k)
{
    viz[k]=1;
    for(int i:g[k])if(!viz[i])dfs(i);
    s.push_back(k);
}
void dfsT(int k,vector<int> &cnt)
{
    cnt.push_back(k);
    viz[k]=1;
    for(int i:gt[k])if(!viz[i])dfsT(i,cnt);
}
inline bool mycomp(const vector<int>&d1,const vector<int>&d2){
    return d1[0]<d2[0];
}
int main()
{
    int n,m,i,j;
    cin>>n>>m;
    viz=new bool[n+1];
    fill(viz,viz+n+1,0);
    while(m--)
    {
        cin>>i>>j;
        g[i].push_back(j);
        gt[j].push_back(i);
    }
    for(i=1; i<=n; ++i)if(!viz[i])dfs(i);
    fill(viz,viz+n+1,0);
    int cnt=0;
    vector<vector<int>>ans;
    int maxi=0;
    for(auto it=s.rbegin(); it!=s.rend(); ++it)if(!viz[*it])
        {
            ans.push_back(vector<int>(0));
            dfsT(*it,ans.back());
            sort(ans.back().begin(),ans.back().end());
        }
    sort(ans.begin(),ans.end(),mycomp);
    cout<<ans.size()<<'\n';
    for(auto p:ans)
    {
        for(auto o:p)cout<<o<<' ';
        cout<<'\n';
    }
    return 0;
}