Mai intai trebuie sa te autentifici.
Cod sursa(job #2780090)
Utilizator | Data | 5 octombrie 2021 22:49:38 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 10 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.42 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<int> v[100100];
vector<int> w[100100];
int vizitat[100100];
stack<int> stiva;
int ctc;
vector<int> ans[100100];
int nou[100100], cnt;
void dfs(int nod)
{
vizitat[nod] = true;
for(auto it : v[nod])
{
if(!vizitat[it])
{
dfs(it);
}
}
stiva.push(nod);
}
void postdfs(int nod)
{
vizitat[nod] = true;
ans[ctc].push_back(nod);
for(auto it : w[nod])
{
if(!vizitat[it])
{
postdfs(it);
}
}
}
int main()
{
fin >> n >> m;
while(m--)
{
int x, y;
fin >> x >> y;
v[x].push_back(y);
w[y].push_back(x);
}
for(int i = 1; i <= n; i ++)
{
if(!vizitat[i])
{
dfs(i);
}
}
while(!stiva.empty())
{
nou[++cnt] = stiva.top();
stiva.pop();
}
for(int i = 1; i <= n; i ++)
{
vizitat[i] = false;
}
for(int i = 1; i <= cnt; i ++)
{
if(!vizitat[i])
{
ctc++;
postdfs(i);
}
}
fout << ctc << '\n';
for(int i = 1; i <= ctc; i ++)
{
for(auto it : ans[i])
{
fout << it << ' ';
}
fout << '\n';
}
return 0;
}