Pagini recente » Cod sursa (job #2433460) | Cod sursa (job #2435073) | Cod sursa (job #2663526) | Cod sursa (job #873422) | Cod sursa (job #2667228)
#include <fstream>
#include <iostream>
#include <vector>
#define nmax 200005
using namespace std;
vector<int> adj_list[nmax], adj_list_transpus[nmax], ordered_list, comp[nmax];
int visited[nmax], comp_nod[nmax];
int nrcomp;
void dfs(int nod) {
if (visited[nod])
return ;
//cout << nod << " ";
visited[nod] = 1;
for (auto &vec : adj_list[nod]) {
dfs(vec);
}
ordered_list.push_back(nod);
}
void dfs_comp(int nod, int index)
{
if(comp_nod[nod])
return;
comp_nod[nod] = index;
comp[index].push_back(nod);
for(auto it: adj_list_transpus[nod])
{
dfs_comp(it, index);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
f >> n >> m;
while(m--)
{
int a, b;
f >> a >> b;
adj_list[a].push_back(b);
adj_list_transpus[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
}
}
/*for(auto it: ordered_list)
{
cout << it << " ";
}*/
for(int i = n - 1; i >= 0; i--)
{
if(!comp_nod[ordered_list[i]]) {
dfs_comp(ordered_list[i], ++nrcomp);
}
}
g<< nrcomp << "\n";
for(int i = 1; i <= nrcomp; i++)
{
for(auto it: comp[i])
{
g << it << " ";
}
g<< '\n';
}
}