Pagini recente » Cod sursa (job #1516507) | Cod sursa (job #3000745) | Cod sursa (job #926273) | Cod sursa (job #2050501) | Cod sursa (job #3210715)
#include <bits/stdc++.h>
#define NMAX 100000
#define ll long long
#define MOD 666013
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
vector<int> adj[NMAX+1];
vector<int> inv[NMAX+1];
vector<int> res[NMAX+1];
int ctc[NMAX+1];
stack<int> S;
bool v[NMAX+1];
int k=0;
void dfs1(int node)
{
v[node]=1;
for(int i : adj[node])
{
if(!v[i])
{
dfs1(i);
}
}
S.push(node);
}
void dfs2(int node)
{
ctc[node]=k;
for(int i : inv[node])
{
if(!ctc[i])
{
dfs2(i);
}
}
}
int main()
{
fin >> n >> m;
for(int i=1;i<=m;i++)
{
int a,b;
fin >> a >> b;
adj[a].push_back(b);
inv[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(!v[i])
{
dfs1(i);
}
}
while(!S.empty())
{
if(!ctc[S.top()])
{
++k;
dfs2(S.top());
}
S.pop();
}
for(int i=1;i<=n;i++)
{
res[ctc[i]].push_back(i);
}
fout << k << "\n";
for(int i=1;i<=k;i++)
{
for(int j : res[i])
{
fout << j << " ";
}
fout << "\n";
}
}