Mai intai trebuie sa te autentifici.
Cod sursa(job #2569145)
| Utilizator | Data | 4 martie 2020 11:16:25 | |
|---|---|---|---|
| Problema | Componente tare conexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.17 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G[100001];
vector <int> GT[100001];
vector <int> rezultat[100001];
stack < int > stiva;
int n,m,a,b,viz[100001],nrctc;
int dfs(int i){
viz[i]=1;
for(auto j:G[i]){
if(viz[j]==0){
dfs(j);
}
}
stiva.push(i);
}
int dfst(int i){
viz[i]=2;
//cout<<i<<" ";
rezultat[nrctc].push_back(i);
for(auto j:GT[i]){
if(viz[j]==1){
dfst(j);
}
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++){
f>>a>>b;
G[a].push_back(b);
GT[b].push_back(a);
}
//cout<<1;
for(int i=1;i<=n;i++){
if(viz[i]==0)dfs(i);
}
//cout<<1;
//cout<<1;
while(!stiva.empty()){
int i=stiva.top();
//cout<<i<<'\n';
if(viz[i]==1){
nrctc++;
dfst(i);
}
stiva.pop();
}
g<<nrctc<<'\n';;
for(int i=1;i<=nrctc;i++){
for(auto j:rezultat[i]){
g<<j<<" ";
}
g<<'\n';
}
}
//v[ictor]
