Pagini recente » Cod sursa (job #1396393) | Cod sursa (job #2449735) | Cod sursa (job #2179990) | Cod sursa (job #2924851) | Cod sursa (job #3159815)
#include <bits/stdc++.h>
using namespace std;
vector<int>edges[200005];
vector<int>components[100005];
vector<int>mirror[200005];
int lista[100005];
bool seen[100005];
int viewed[100005];
int cnt=0, counter=0;
void dfs(int a)
{
seen[a]=1;
for (auto it:edges[a])
{
if (!seen[it])
dfs(it);
}
lista[++counter]=a;
}
void dfs2(int a)
{
viewed[a]=cnt;
for (auto it:mirror[a])
{
if (viewed[it]==0)
dfs2(it);
}
}
int main()
{
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
int n, m, a, b;
cin>>n>>m;
for (int i=1; i<=m; i++)
{
cin>>a>>b;
edges[a].push_back(b);
}
for (int i=1; i<=n; i++)
if (!seen[i])
dfs(i);
///inservam muchiile
for (int i=1; i<=n; i++)
{
for (int j=0; j<edges[i].size(); j++)
{
mirror[edges[i][j]].push_back(i);
}
}
for (int i=n; i>=1; i--)
{
if (!viewed[lista[i]])
{
cnt++;
dfs2(lista[i]);
}
///cout<<viewed[lista[i]]<<" ";
}
///cout<<'\n';
for (int i=1; i<=n; i++)
{
components[viewed[i]].push_back(i);
}
cout<<cnt<<'\n';
for (int i=1; i<=cnt; i++)
{
for (int j=0; j<components[i].size(); j++)
{
cout<<components[i][j]<<" ";
}
cout<<'\n';
}
}