Pagini recente » Cod sursa (job #3318876) | Cod sursa (job #3321606) | Cod sursa (job #3326767) | Cod sursa (job #3317233) | Cod sursa (job #3344349)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
const int nmax=1e5, mmax=2e5;
vector<int> G[nmax+1], GT[nmax+1];
int timeFin[nmax+1], cnt=1;
bool visited[nmax+1];
vector<vector<int>> componente;
void dfs(int s)
{
stack<int> stiva;
stiva.push(s);
visited[s]=true;
int t;
while(!stiva.empty())
{
t=stiva.top();
while(!G[t].empty() && visited[G[t].back()])
G[t].pop_back();
if(!G[t].empty())
{
visited[G[t].back()]=true;
stiva.push(G[t].back());
G[t].pop_back();
}
else
{
timeFin[cnt++]=t;
stiva.pop();
}
}
}
void identificareComponente(int s)
{
queue<int> coada;
vector<int> ans;
coada.push(s);
visited[s]=true;
int t;
while(!coada.empty())
{
t=coada.front();
ans.push_back(t);
coada.pop();
for(int x: GT[t])
if(!visited[x])
{
coada.push(x);
visited[x]=true;
}
}
componente.push_back(ans);
}
int main()
{
fin >> n >> m;
int a, b;
for(int i=0; i<m; i++)
{
fin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
for(int i=1; i<=n; i++)
if(!visited[i])
dfs(i);
for(int i=1; i<=n; i++)
visited[i]=false;
int nrComponente=0;
for(int i=n; i>=1; i--)
if(!visited[timeFin[i]])
{
nrComponente++;
identificareComponente(timeFin[i]);
}
fout << nrComponente << '\n';
for(vector<int> ans: componente)
{
for(int x: ans)
fout << x << ' ';
fout << '\n';
}
return 0;
}