Pagini recente » Cod sursa (job #2990666) | Cod sursa (job #1975196) | Cod sursa (job #2030260) | Cod sursa (job #1817324) | Cod sursa (job #3309704)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=1e5;
int n,m,i,node1,node2,sol;
bool viz[NMAX+5];
vector <int> edge[NMAX+5],t_edge[NMAX+5],comp_conex[NMAX+5];
stack <int> s;
void dfs(int node)
{
viz[node]=1;
for (auto x: edge[node])
if (!viz[x])
dfs(x);
s.push(node);
}
void t_dfs(int node)
{
viz[node]=1;
comp_conex[sol].push_back(node);
for (auto x: t_edge[node])
if (!viz[x])
t_dfs(x);
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
fin>>n>>m;
while (m--)
{
fin>>node1>>node2;
edge[node1].push_back(node2);
t_edge[node2].push_back(node1);
}
for (i=1; i<=n; i++)
{
if (!viz[i])
dfs(i);
}
for (i=1; i<=n; i++)
viz[i]=0;
while (!s.empty())
{
node1=s.top();
s.pop();
if (viz[node1])
continue;
sol++;
t_dfs(node1);
}
fout<<sol<<'\n';
for (i=1; i<=sol; i++)
{
for (auto x: comp_conex[i])
fout<<x<<" ";
fout<<'\n';
}
return 0;
}