Mai intai trebuie sa te autentifici.
Cod sursa(job #3268639)
Utilizator | Data | 16 ianuarie 2025 16:27:45 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.89 kb |
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int > G1[50005],G2[50005],v[50005];
stack < int > s ;
int n,m,x,y,vis1[50005],vis2[50005],p,nr;
void dfs1(int k)
{ vis1[k]=1;
for(int i : G1[k])
{
if(!vis1[i])
dfs1(i);
}
s.push(k);
}
void dfs2(int k)
{vis2[k]=1;
for(int i : G2[k])
{
if(!vis2[i])
dfs2(i);
}
v[nr].push_back(k);
}
int main()
{f>>n>>m;
for(int i=1;i<=m;++i)
{
f>>x>>y;
G1[x].push_back(y);
G2[y].push_back(x);
}
for(int i=1;i<=n;++i)
{
if(!vis1[i])
dfs1(i);
}
while(!s.empty())
{
p=s.top();
if(!vis2[p])
{
nr++;
dfs2(p);
}
s.pop();
}
g<<nr<<'\n';
for(int i=1;i<=nr;++i)
{
for(int j :v[i])
g<<j<<" ";
g<<'\n';
}
return 0;
}