Pagini recente » Cod sursa (job #1830099) | Cod sursa (job #2448243) | Cod sursa (job #2806642) | Cod sursa (job #2138125) | Cod sursa (job #2674452)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define nmax 1000000
#define MMAX 100000
#define inf 1e18
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> adj[100005];
int n,m,low_link[100005],idx[100005],cnt=0,ctc=0;
bool viz[100005],instack[100005];
vector<int> sol[100005];
stack<int> s;
void dfs(int node)
{
s.push(node);
instack[node]=true;
idx[node]=low_link[node]=++cnt;
for(auto x:adj[node])
{
if(idx[x]==0) {dfs(x);}
if(instack[x]==1)
{
low_link[node]=min(low_link[node],low_link[x]);
}
}
if(idx[node]==low_link[node])
{
ctc++;
int x=node;
do
{
x=s.top();
low_link[x]=idx[node];
sol[ctc].pb(x);
instack[x]=0;
s.pop();
}
while(x!=node);
}
}
int main()
{
f>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
f>>x>>y;
adj[x].pb(y);
}
for(int i=1; i<=n; i++)
{
if(idx[i]==0)
{
dfs(i);
}
}
g<<ctc<<'\n';
for(int i=1;i<=ctc;i++)
{
for(auto x:sol[i])
{
g<<x<<" ";
}
g<<'\n';
}
}