Pagini recente » Cod sursa (job #1457723) | Cod sursa (job #1984365) | Cod sursa (job #841403) | Cod sursa (job #2547458) | Cod sursa (job #3143737)
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cstdlib>
#include <string>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>scc;
int cnt=0;
void DFS(int node,vector<vector<int> >&adj,bool visit[])
{
visit[node]=true;
scc.push_back(node+1);
for(int i=0;i<adj[node].size();i++)
{
if(!visit[adj[node][i]])
{
DFS(adj[node][i],adj,visit);
}
}
}
void FillStack(int node,vector<vector<int> >&adj,bool visit[],stack<int>&q)
{
visit[node]=true;
for(int i=0;i<adj[node].size();i++)
{
if(!visit[adj[node][i]])
{
FillStack(adj[node][i],adj,visit,q);
}
}
q.push(node);
}
void GetSCCs(vector<vector<int> >&adj,int n)
{
stack<int>q;
bool visit[100001];
for(int i=0;i<=100000;i++)
{
visit[i]=0;
}
for(int i=0;i<n;i++)
{
if(!visit[i])
{
FillStack(i,adj,visit,q);
}
}
vector<vector<int> >transp(n);
for(int i=0;i<n;i++)
{
for(int j=0;j<adj[i].size();j++)
{
transp[adj[i][j]].push_back(i);
}
}
for(int i=0;i<n;i++)
{
visit[i]=false;
}
while(!q.empty())
{
int node=q.top();
q.pop();
if(!visit[node])
{
DFS(node,transp,visit);
if(scc[scc.size()-1]==-1);
else
{
scc.push_back(-1);
cnt++;
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
vector<vector<int> >adj(n);
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
adj[a-1].push_back(b-1);
}
GetSCCs(adj,n);
cout<<cnt<<"\n";
for(int i=0;i<scc.size();i++)
{
if(scc[i]==-1)
{
cout<<"\n";
}
else
{
cout<<scc[i]<<" ";
}
}
return 0;
}