Pagini recente » Borderou de evaluare (job #178049) | Cod sursa (job #576997) | Cod sursa (job #2546495) | Cod sursa (job #2912871) | Cod sursa (job #2972576)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, numComponents=1;
vector <int> og[NMAX], tg[NMAX];
stack <int> st;
bool visited[NMAX];
//int component[NMAX];
vector <int> components[NMAX];
void dfs_1(int x)
{
visited[x]=true;
for(int i: og[x])
if(!visited[i]) dfs_1(i);
st.push(x);
}
void dfs_2(int x)
{
//cout<<x<<" ";
//component[x] = numComponents;
components[numComponents].push_back(x);
visited[x]=true;
for(int i: tg[x])
if(!visited[i]) dfs_2(i);
}
void Kosaraju()
{
for(int i=1; i<=n; i++)
if(!visited[i]) dfs_1(i);
for(int i=1; i<=n; i++)
visited[i]=false;
while (!st.empty())
{
int v=st.top();
st.pop();
if (!visited[v])
{
dfs_2(v);
numComponents++;
//printf("\n");
}
}
}
int main()
{
fin>>n>>m;
int a, b;
for(int i=1; i<=m; ++i)
{
fin>>a>>b;
og[a].push_back(b);
tg[b].push_back(a);
}
Kosaraju();
fout<<numComponents-1<<endl;
for(int i=1; i<=numComponents; ++i, fout<<endl)
for(int j: components[i])
fout<<j<<" ";
return 0;
}