Pagini recente » Cod sursa (job #1203145) | Cod sursa (job #2228807) | Cod sursa (job #61897) | Cod sursa (job #135495) | Cod sursa (job #2722164)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 2e9
#define NMAX 150005
#define PMAX 3500
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,cnt=0,index1[100005],low_link[100005],ctc;
vector<int> adj[100005],sol[100005];
bool viz[100005],instack[100005];
stack<int> s;
void dfs(int node)
{
s.push(node);
instack[node]=1;
index1[node]=low_link[node]=++cnt;
for(int i=0; i<adj[node].size(); i++)
{
int vec=adj[node][i];
if(index1[vec]==0)
{
dfs(vec);
}
if(instack[vec]==1)
{
low_link[node]=min(low_link[node],low_link[vec]);
}
}
if(index1[node]==low_link[node])
{
ctc++;
int x=node;
do
{
x=s.top();
low_link[x]=low_link[node];
sol[ctc].pb(x);
s.pop();
instack[x]=0;
}
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(index1[i]==0)
{
dfs(i);
}
}
g<<ctc<<'\n';
for(int i=1;i<=ctc;i++)
{
for(int j=0;j<sol[i].size();j++)
{
g<<sol[i][j]<<" ";
}
g<<'\n';
}
}